Climbing Stairs
Count the ways to climb n steps taking 1 or 2 at a time. The ways to reach step n equal the ways to reach n−1 plus n−2 — the Fibonacci recurrence.
- Category
- Dynamic Programming
- Time complexity
- O(n)
- Space complexity
- O(n)
Pseudocode
dp[0] = dp[1] = 1 dp[i] = dp[i−1] + dp[i−2] answer at dp[n]
Reference implementation
dp = [1, 1]
for i in range(2, n+1):
dp.append(dp[i-1] + dp[i-2])