Easy Tabulation Dynamic Programming
In plain English: Count the number of different ways to reach the top of a staircase if you can take 1 or 2 steps at a time.
To reach step n you came from step n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2) — the same recurrence as Fibonacci.
Prompt
You can climb 1 or 2 steps at a time. How many distinct ways can you climb n stairs?
Try to write it from scratch before scrolling down.
Solution
def climb_stairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b # ways[i] = ways[i-1] + ways[i-2]
return b
# Test: climb_stairs(2) == 2
# Test: climb_stairs(3) == 3
# Test: climb_stairs(5) == 8