Climbing Stairs
Problem
n steps. On every move you climb either 1 or
2 steps. Count how many distinct sequences of moves take you from the ground
exactly to the top.n = 2Output2 (1+1, 2)n = 3Output3 (1+1+1, 1+2, 2+1)1 ≤ n ≤ 45 · answer fits in a 32-bit int
Try it yourself
class Solution {
public int climbStairs(int n) {
}
}
n either from
n-1 or from n-2. So ways(n) = ways(n-1) + ways(n-2)
— it is Fibonacci, and only the last two values are ever needed.Instinct The best answer at position i depends only on a few earlier positions (i-1, i-2, ...) - write dp[i] from its predecessors, then roll it into variables.
Memory hack Look back, pick best, roll forward - every step only remembers the last couple of stairs it stood on.
Open the 1-D Dynamic Programming guide →Approaches
Brute ForcePlain Recursion
O(2n)Space O(n)Directly code the recurrence: from step i try a 1-step and a
2-step move and add the counts. The call tree branches twice per level and recomputes
the same steps over and over (ways(n-2) is solved twice, etc.).
public int climbStairs(int n) { return climb(0, n); } private int climb(int i, int n) { if (i > n) return 0; // overshot the top if (i == n) return 1; // landed exactly on top return climb(i + 1, n) + climb(i + 2, n); }
Correct and tiny, but exponential — n = 45 needs ~109 calls.
BetterTop-Down Memoization
O(n)Space O(n)There are only n+1 distinct states (the current step). Cache each
answer in memo[i] the first time it is computed, so every state is solved
once and the tree collapses to a line.
public int climbStairs(int n) { return climb(0, n, new int[n + 1]); } private int climb(int i, int n, int[] memo) { if (i > n) return 0; if (i == n) return 1; if (memo[i] > 0) return memo[i]; return memo[i] = climb(i + 1, n, memo) + climb(i + 2, n, memo); }
Linear time, but pays O(n) for the memo plus the recursion stack.
OptimalBottom-Up, Two Variables
O(n)Space O(1)Fill the table dp[i] = dp[i-1] + dp[i-2] from the bottom
(dp[0] = dp[1] = 1). Each entry only reads the two before it, so keep just
prev2 and prev1 and slide them forward.
public int climbStairs(int n) { int prev2 = 1, prev1 = 1; // ways(0), ways(1) for (int i = 2; i <= n; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; } return prev1; }
Dry runn = 5 (conceptual dp[0..5])
- init1a1b····ways(0)=ways(1)=1
- i=211a2b···1+1 = 2
- i=3112a3b··2+1 = 3
- i=41123a5b·3+2 = 5
- i=511235a8b5+3 = 8 ✔
Same linear time, constant memory, no recursion — the interview answer.
S,
dp[i] = Σ dp[i-s] over s ∈ S.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Plain Recursion | O(2n) | O(n) |
| Better | Top-Down Memoization | O(n) | O(n) |
| Optimal | Bottom-Up, Two Variables | O(n) | O(1) |
- Missing the overshoot base case (
i > n) — infinite or wrong recursion. - Using
0as “not computed” only works because every answer is ≥ 1. - Returning
prev2instead ofprev1— off by one step.
- Derive the recurrence from the last move; then say “this is Fibonacci”.
- Walk the ladder: recursion → memo → table → two variables.
- Mention O(log n) matrix exponentiation as a follow-up if asked.