# 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

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

Liên hệ Aivivu, đặt vé máy bay tham khảo

ReplyDeletevé máy bay đi Mỹ hạng thương gia

vé máy bay từ mỹ về việt nam mùa dịch

lich bay tu duc ve viet nam

vé máy bay từ nga về việt nam

ve may bay tu anh ve viet nam

lịch bay từ pháp về việt nam

khách sạn cách ly tphcm

chi phí vé máy bay cho chuyên gia nước ngoài