Climbing stairs / Fibonacci
Scenario
You are climbing a staircase with `n` steps. You can either take 1 step or 2 steps at a time. How many distinct ways can you reach the top?
Why it exists
Problem: Generating every possible combination of 1s and 2s that sum to `n` explores the same paths repeatedly, taking exponential O(2^n) time.
Better idea: The number of ways to get to step `i` is simply the sum of the ways to get to step `i-1` (and taking a 1-step) plus the ways to get to step `i-2` (and taking a 2-step). We can just add previous answers together.
Mental model
To get to step `i`, you must have come from either step `i-1` or step `i-2`. Adding those two possibilities gives you the total ways.
This is literally the Fibonacci sequence. The state is just the current step `i`. `dp[i]` represents the number of ways to reach step `i`. The base cases are `dp[1] = 1` and `dp[2] = 2` (or `dp[0]=1, dp[1]=1` depending on indexing), because there's 1 way to climb 1 step, and 2 ways to climb 2 steps. The transition is `dp[i] = dp[i-1] + dp[i-2]`.
Repeated decision: To reach step `i`, did I just take one step from `i-1`, or two steps from `i-2` -- so `dp[i] = dp[i-1] + dp[i-2]`?
Explanation
This problem is the simplest possible DP recurrence and forms the template for 1D Dynamic Programming.
The top-down memoization approach evaluates `climb(i) = climb(i-1) + climb(i-2)` recursively, caching each `i` so it's only computed once. The bottom-up tabulation approach builds an array `dp` from index `1` to `n` in a `for` loop.
Because `dp[i]` only depends on `dp[i-1]` and `dp[i-2]`, we don't even need the full array. We can space-optimize to two rolling variables: `prev1` and `prev2`. We shift these variables forward at each step, yielding an O(n) time, O(1) space algorithm.
Let's hand-trace `n = 5` filling `dp[0]..dp[5]`. We'll use 0-based indexing for steps, defining our base cases as `dp[0] = 1` (standing on the ground) and `dp[1] = 1` (one way to reach step 1).
- `dp[2] = dp[1] + dp[0] = 1 + 1 = 2`
- `dp[3] = dp[2] + dp[1] = 2 + 1 = 3`
- `dp[4] = dp[3] + dp[2] = 3 + 2 = 5`
- `dp[5] = dp[4] + dp[3] = 5 + 3 = 8`
The final array is `[1, 1, 2, 3, 5, 8]`, so there are 8 distinct ways to reach step 5.
Key points
- Complexity: O(n) time, O(1) space (when using rolling variables).
- Base cases: `dp[1] = 1`, `dp[2] = 2`. The recursion must bottom out here so we can build the rest of the steps.
Common mistakes
- Using plain unmemoized recursion: If you don't use a cache (or a bottom-up loop), the recursion tree branches exponentially. `fib(5)` calls `fib(3)` twice and `fib(2)` three times. This results in Time Limit Exceeded (TLE) for even small values of `n`.
- Off-by-one errors with base cases: Make sure you know whether your `n` is 0-indexed or 1-indexed. Sometimes `dp[0]=1` and `dp[1]=1` is easier to loop with than starting at 1 and 2.
Recall questions
- What is the recurrence relation for Climbing Stairs?
- What does `dp[i]` represent in the Climbing Stairs problem?
- How can you optimize the space complexity of Climbing Stairs from O(n) to O(1)?
Questions & answers
Given `n` steps, what if you could take 1, 2, or 3 steps at a time?
The recurrence becomes `dp[i] = dp[i-1] + dp[i-2] + dp[i-3]`, and you would use 3 rolling variables instead of 2.
Approach: Identify that the state is the same, but the transition expands to include the third possibility.
What if certain steps are 'broken' and cannot be stepped on?
Initialize a set of broken steps. During the transition, if `i` is broken, set `dp[i] = 0`.
Approach: Modify the transition logic: a broken step has 0 ways to reach it, effectively blocking paths through it.
Continue learning
Previous: State & transition
Previous: Space optimization
Next: House robber