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

Reference : http://ms.appliedprobability.org/data/files/Articles%2047/47-1-4.pdf