-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathstair.py
More file actions
46 lines (36 loc) · 787 Bytes
/
stair.py
File metadata and controls
46 lines (36 loc) · 787 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#stair problems
#number of steps
N=int(input())
#possible steps that could be taken
lst=[1,3,5]
dp=[[0 for i in range(5)] for j in range(len(lst))]
# print(dp)
def count(step,n):
ans=0
#base conditions
if n<0:
return 0
if n==0:
# print(dp)
return 1
if dp[step-1][n]:
return dp[step-1][n]
# print(dp)
#main rec call
ct=0
for st in lst:
# print(st)
ct=count(st,n-st)
ans+=ct
# print(st,"::",dp,"::",n)
if n-st>0:
dp[st-1][n-st]+=ct
print(st,"::",dp,"::",n)
return ans
# print(dp)
ways=0
for st in lst:
ways+=count(st,N-st)
#ways in which we can reach the top stair using given steps
print("WAYS:::"," ",ways)
# print(count(3,1))