LeetCode #70 — Climbing Stairs: Fibonacci in disguise

Problem (LeetCode #70, Easy): You're climbing a staircase with n steps. Each move climbs either 1 or 2 steps. How many distinct ways can you reach the top? (1 ≤ n ≤ 45)

The naive instinct

Think about the last move you make. You arrived at step n either from step n-1 (a 1-step) or from step n-2 (a 2-step). Those are the only options, and they're mutually exclusive — so:

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

with ways(1) = 1 and ways(2) = 2. Translate that directly into code:

def climbStairs(n):
    if n <= 2:
        return n
    return climbStairs(n - 1) + climbStairs(n - 2)

Correct — and doomed. Each call spawns two more, so it's O(2ⁿ). At the constraint ceiling n = 45, that's billions of calls, almost all of them recomputing answers we already knew. ways(40) alone gets recomputed tens of thousands of times.

The reframe: never solve the same subproblem twice

The call tree is huge, but it only contains 45 distinct questions. So cache every answer the first time you compute it. My first accepted version did exactly that — but clumsily, with separate if n-1 not in self.memory / if n-2 not in self.memory guards before each recursive call (and a leftover dead variable from an abandoned approach — we've all been there).

Accepted isn't the finish line. The insight that cleans it up: put the cache check at the top of the function, and the guards become unnecessary — every call protects itself:

class Solution:
    memory = {1: 1, 2: 2}
 
    def climbStairs(self, n: int) -> int:
        if n in self.memory: return self.memory[n]
        self.memory[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
        return self.memory[n]

Four lines of logic. Every subproblem computed exactly once: O(n) time, O(n) space for the cache plus recursion stack. Same complexity as my first version — but the reviewer-you-interview-with sees the difference immediately.

Now look at the sequence the recurrence produces: 1, 2, 3, 5, 8, 13… — it's Fibonacci wearing a staircase costume. "Count the ways" problems collapse into recurrences more often than you'd expect.

The finishing move: O(1) space

Once you see the recurrence only ever looks back two steps, you don't need the dict or the recursion — just two rolling variables:

def climbStairs(n):
    if n <= 2:
        return n
    a, b = 1, 2          # ways(1), ways(2)
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Complexity

The pattern to remember

When a problem asks "how many distinct ways to reach X", enumerate the possible last moves and sum the ways of what remains — that's your recurrence, and memoization (or a bottom-up loop) makes it linear. This exact skeleton solves House Robber, Decode Ways, Min Cost Climbing Stairs, and half the "easy DP" bucket. Climbing Stairs is just the friendliest doorway into it.