There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters. For example, if N is 4, then there are 5 unique ways:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X.
Solution: In Python 3
def staircase(n, X):
if n < 0:
return 0
elif n == 0:
return 1
elif n in X:
return 1 + sum(staircase(n - x, X) for x in X if x < n)
else:
return sum(staircase(n - x, X) for x in X if x < n)
X = [1,3,5]
n=4
print(staircase(n,X))Also Checkout