70. Climbing Stairs

Climbing Stairs is the friendliest introduction to dynamic programming there is — the whole problem is one small recurrence, and seeing where it comes from is worth more than memorizing the code. It’s part of the dynamic programming pattern, so if the recurrence here clicks, a dozen harder DP problems get easier.

The problem

You’re climbing a staircase with n steps, and each move takes you up either 1 step or 2. The question is how many distinct sequences of moves get you to the top. (Full statement on LeetCode.)

For n = 3 there are three ways: 1+1+1, 1+2, and 2+1. For n = 4 there are five. Those counts — 1, 2, 3, 5, 8… — are the giveaway.

Intuition: it’s Fibonacci in disguise

Look only at the last move that reaches step n. It was either a 1-step (so you came from step n-1) or a 2-step (from step n-2) — and those two cases can never overlap, because the size of that final move is different. So every way of reaching the top is either “a way to reach n-1, then step 1” or “a way to reach n-2, then step 2”:

$\text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2)$

That’s the Fibonacci recurrence, with base cases ways(1) = 1 and ways(2) = 2. Naming the subproblem — ways to reach step i — is the entire trick; the code just fills it in.

Solution

Top-down first, since it reads like the recurrence. Cache each answer so the exponential recursion collapses to one value per step:

class Solution {
    public int climbStairs(int n) {
        return climb(n, new int[n + 1]);
    }

    private int climb(int i, int[] memo) {
        if (i <= 2) return i;              // ways(1)=1, ways(2)=2
        if (memo[i] != 0) return memo[i];  // already computed
        memo[i] = climb(i - 1, memo) + climb(i - 2, memo);
        return memo[i];
    }
}

Bottom-up is where you notice each answer needs only the previous two, so you don’t need the whole array — just two rolling variables:

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;          // ways(1), ways(2)
        for (int i = 3; i <= n; i++) {
            int cur = prev1 + prev2;       // ways(i) = ways(i-1) + ways(i-2)
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Complexity

Approach	Time	Space
Memoized recursion	$O(n)$	$O(n)$
Bottom-up, rolling	$O(n)$	$O(1)$

Both are linear time; the rolling version wins on space because it throws away every step older than the last two.

In an interview

State the recurrence before you write anything: “the last move is a 1 or a 2, so ways(n) = ways(n-1) + ways(n-2).” That one sentence shows you found the subproblem, which is what’s actually being graded. Then offer the rolling $O(1)$-space version as the follow-up — interviewers almost always ask for it once the array solution is on the board.

The same “reach this state from one or two steps back” shape drives House Robber and a whole family of one-dimensional DP; the pattern hub walks through where it recurs.

References

• LeetCode 70 — Climbing Stairs