Staircase problem : Recursive and Dynamic programming solution (Sample code in Python)

Problem:- Top of staircases can be reached by climbing 1,2 or 3 steps at a time.How many ways there are to reach the top of the staircase. i.e: find number of ways to climb top of staircase.

Sample program to count total number of ways to reach top of staircase:- Recursive and Dynamic programming approach

#find number of ways to reach at top of staircase with 1, 2 or 3 steps
def find_staircase_recur(n):
if n ==0 or n ==1:
return 1;
elif n==2 : #(1,1|2) 2 ways
return 2;
elif n == 3: #(1,2| 1,1,1|2,1|3) 4 ways
return 4
else :
return find_staircase(n-1) + find_staircase(n-2) + find_staircase(n-3)

#build dp table in bottom-up approach
def find_staircase_dp(n):
table=[]
#insert base case
table.insert(0,1);
table.insert(1,1);
table.insert(2,2); #(1,1|2) 2 ways
table.insert(3,4); #(1,2| 1,1,1|2,1|3) 4 ways
#Iterate if N >= 4
for i in range(4,n+1):
val = table[i-1] + table[i-2] +table[i-3]
table.insert(i,val);
return table[n]
print "Enter height of stair(Number of steps)"
n = int(raw_input().strip())
print "Number of ways to reach top of stair using 1, 2 or 3 steps are: "
print find_staircase_dp(n)

Explanation:- function find_staircase_recur is recursive way of counting no of ways and function find_staircase_dp is using bottom-up memoization approach to build DP table and remember pre-computed value.

Sample output
:-
>>>
Enter height of stair(Number of steps)
7
Number of ways to reach top of stair using 1, 2 or 3 steps are:
44

>>>
Enter height of stair(Number of steps)
9
Number of ways to reach top of stair using 1, 2 or 3 steps are:
149

Referencehttp://ms.appliedprobability.org/data/files/Articles%2047/47-1-4.pdf
Location: Hyderabad, Telangana, India