Interview challenge · easy · dynamic-programming, fibonacci
Climbing Stairs
The challenge
You are climbing a staircase that takes n steps to reach the top. Each time you can climb either 1 or 2 steps. In how many distinct ways can you climb to the top?
Example
n = 2 -> 2 (1+1, 2)
n = 3 -> 3 (1+1+1, 1+2, 2+1)
n = 5 -> 8Idea: the last move is either 1 or 2 steps, so ways(n) = ways(n-1) + ways(n-2): Fibonacci. Keep only the last two values. Time O(n), space O(1).
The solution
# Climbing Stairs - ayotl.dev
def climb(n):
# ways(n) = ways(n-1) + ways(n-2):
# the last move was 1 or 2 steps.
# That is Fibonacci!
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a
for n in [2, 3, 5, 10, 45]:
print(n, climb(n))
$ python3 climbing_stairs.py
2 2
3 3
5 8
10 89
45 1836311903