Climbing Stairs
You are climbing a staircase. It takes `n` steps to reach the top. Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top? **Core Insight:** The number of ways to reach step `n` is the sum of ways to reach step `n-1` (take one more step) and step `n-2` (take two more steps). This is exactly the Fibonacci recurrence: `dp[n] = dp[n-1] + dp[n-2]`, with base cases `dp[1] = 1` and `dp[2] = 2`. **Algorithm:** Space-optimised DP using two variables. Start with `a = 1, b = 2`. For each step from 3 to n compute `c = a + b`, then shift `a = b, b = c`. Return `b` (or `a` when n = 1). **Why it works:** Every path to step n must arrive from either step n-1 or step n-2. Summing those counts gives all distinct paths without double-counting. **Complexity:** Time O(n) — one loop. Space O(1) — two integer variables.
Constraints
- •
1 ≤ n ≤ 45
def climbStairs(n: int) -> int:
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b