LeetCode 70 – Climbing Stairs

Climbing Stairs is Fibonacci wearing a hard hat, and it is on nearly every interview list because it is the smallest problem where the recursion-to-DP conversation happens naturally. The answer is three lines. What is being tested is the route you take to get there, and there is a specific trap in the naive version worth walking into deliberately.

The problem

You are climbing a staircase of n steps. Each time you can climb either 1 or 2 steps. How many distinct ways can you reach the top?

n = 2  -> 2      1+1,  2
n = 3  -> 3      1+1+1,  1+2,  2+1
n = 4  -> 5
n = 1  -> 1
n = 5  -> 8

1, 2, 3, 5, 8 — Fibonacci, offset by one. Noticing that is nice; being able to say why it is Fibonacci is the actual answer, because the "why" is the recurrence and the recurrence is what survives when the problem is changed.

The recurrence

Same question as the grid problems: what was the last move? To be standing on step n, the final step was either a 1 (from step n-1) or a 2 (from step n-2). Those are the only two options and they cannot overlap, since they end differently.

ways(n) = ways(n-1) + ways(n-2)
ways(1) = 1
ways(2) = 2

ways(0) = 1 also works and is arguably cleaner — there is exactly one way to stand at the bottom having climbed nothing, the empty sequence. Interviewers occasionally push on whether the empty path counts; "one way, the do-nothing way" is the answer, and it is the same convention that makes 0! = 1.

The trap in the naive recursion

Writing the recurrence directly gives an exponential algorithm, and it is worth seeing why rather than being told:

           ways(5)
        /          \
    ways(4)        ways(3)
    /     \        /     \
 ways(3) ways(2) ways(2) ways(1)
  ...

ways(3) computed twice, ways(2) three times, and it doubles with every step.

The subproblems overlap. That single observation is what makes this dynamic programming rather than plain recursion, and it is the distinction the problem exists to teach: a recursion whose subproblems are all distinct is just divide and conquer, and memoising it buys nothing.

The fix has two shapes. Memoise the recursion top-down and each value is computed once. Or build bottom-up from the base cases and skip the call stack entirely — which is what you should write, because the recurrence only ever looks two steps back, so the whole table collapses to two variables.

Java

class Solution {
    public int climbStairs(int n) {
        int twoBack = 1;   // ways(0): the do-nothing path
        int oneBack = 1;   // ways(1)

        for (int i = 2; i <= n; i++) {
            int current = oneBack + twoBack;
            twoBack = oneBack;
            oneBack = current;
        }

        return oneBack;
    }
}

Seeding both at 1 makes n = 1 and n = 0 fall out without a guard: the loop simply does not run. Name the variables for what they hold rather than a and b — the assignment order in a two-variable rotation is where this gets written wrong under pressure, and readable names are how you catch it.

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        two_back, one_back = 1, 1

        for _ in range(2, n + 1):
            two_back, one_back = one_back, one_back + two_back

        return one_back

Tuple assignment removes the temporary and, more usefully, removes the ordering bug — the whole right-hand side is evaluated before anything is rebound, so there is no half-updated state to get wrong.

Complexity

The exponential base is the golden ratio rather than 2, because the tree is lopsided — but "exponential" is the point and O(2ⁿ) as a loose upper bound is a fine thing to say. There is also an O(log n) solution by matrix exponentiation, and a closed form via Binet's formula. Both are real; the closed form loses precision in floating point well before n gets interesting, which is the more useful thing to know about it.

The follow-up that separates people

"What if you could climb 1, 2 or 3 steps?" — add a third term. "What if the allowed step sizes are an arbitrary set?" — the recurrence becomes a sum over that set, the rolling window grows to the largest step, and the problem is now Coin Change (322) counting combinations.

That generalisation is the reason to derive the recurrence rather than recognise Fibonacci. Someone who pattern-matched to Fibonacci has nothing to adapt; someone who asked "what was the last move?" changes one line.

Note the ordering subtlety when it does become Coin Change: here 1+2 and 2+1 are different ways, so it counts permutations. Coin Change II counts combinations, and the difference is which loop is on the outside. Getting that backwards is the classic bug in the generalised version.

What the interviewer is checking

• That you derive f(n) = f(n-1) + f(n-2) from the last move.
• That you can name the overlapping subproblems, and say why that means DP.
• Base cases, including whether ways(0) is 1 and why.
• That you compress to O(1) space rather than keeping the array.
• The two-variable rotation, written in the right order.
• That you can generalise to arbitrary step sizes, and know it counts permutations.