Dynamic Programming · LC #70
Climbing Stairs
Count distinct ways to climb n stairs taking 1 or 2 steps at a time. The recurrence is identical to Fibonacci: ways(n) = ways(n-1) + ways(n-2).
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
You can climb 1 or 2 steps at a time. How many distinct ways can you climb `n` stairs?
Sample I/O
Input: n = 2 Output: 2 (1+1, 2) Input: n = 3 Output: 3 (1+1+1, 1+2, 2+1)
Intuition
How to Think About It
Intuition
DP works because the number of ways to reach stair n depends only on stair n-1 and n-2 - optimal substructure with overlapping subproblems. Memoising or tabulating those two sub-results eliminates exponential recomputation.
Core Concept
Recurrence: dp[n] = dp[n-1] + dp[n-2]. Base cases: dp[1]=1, dp[2]=2. Space-optimise with two rolling variables instead of an array.
When to use
Any counting problem where each step has a fixed set of choices that depend only on recent history - staircase variants, tiling, frog jump.
When NOT to use
When the number of choices per step varies with position and cannot be reduced to a fixed-width recurrence; use BFS or combinatorics instead.
Key Insights
What to Know Cold
- Climbing Stairs is Fibonacci with a 1-index shift: climbStairs(n) = fib(n+1).
- Rolling two variables (prev2, prev1) is sufficient - no array needed.
- Base cases must handle n=1 and n=2 explicitly before the loop.
- Generalises to k-step variant: keep a rolling window of size k and sum it.
- Overlapping subproblems are the reason naive recursion is O(2^n) - DP brings it to O(n).
1 example
Worked Examples
Count ways to climb 5 stairs
n=5; each step can be 1 or 2 stairs.
Fibonacci-style rolling variables, O(n) time O(1) space.
Output: 8
Gateway DP problem that establishes the Fibonacci recurrence pattern used in dozens of harder problems (House Robber, Unique Paths, etc.).