Climbing Stairs: from exponential recursion to O(1) space

The first time I solved Climbing Stairs I wrote the obvious recursion, hit submit, and watched it crawl. That timeout is the entire lesson. The problem reads like a counting puzzle, but it is Fibonacci wearing a staircase costume — and once you see that, every optimisation that follows is forced rather than clever.

The problem in one line

You climb a staircase of n steps, taking 1 or 2 steps at a time. Count the distinct orderings that get you to the top. The only constraint that matters: n <= 45.

That bound is a hint, not a detail. The answer at n = 45 is the 46th Fibonacci number — big, but it fits in a 64-bit integer, and n is small enough that almost any approach runs. The interesting question is which approach you would write if this were a code review, not a contest.

Why the naive recursion deserves to time out

Stand on step n and look back. You got here either from step n-1 with a single step, or from step n-2 with a double. Those are the only two ways to arrive, and they never overlap. So the count splits cleanly:

ways(n) = ways(n-1) + ways(n-2), with ways(1) = 1 and ways(2) = 2.

That is the recurrence, and the direct translation is honest code:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

It is also O(2^n). Each call spawns two more, and the tree is full of repeats — ways(10) gets recomputed thousands of times on the way down. The recurrence is right; the execution is doing exponential work for a linear problem. It should time out, and when it does, that is the algorithm telling you it has no memory.

Memoize it and the cost collapses

Give the recurrence a place to remember answers it has already computed, and the duplicate subtrees vanish:

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}
        def ways(k: int) -> int:
            if k <= 2:
                return k
            if k not in memo:
                memo[k] = ways(k - 1) + ways(k - 2)
            return memo[k]
        return ways(n)

Now every value from 1 to n is computed exactly once: O(n) time, O(n) space for the cache plus the call stack.

I rarely ship this version, though. Memoization is the right teaching step — it shows you precisely what the naive code was wasting — but for a recurrence this shallow, recursion buys nothing and quietly risks the stack. The bottom-up rewrite is shorter and has no stack at all.

The version I actually write

You never need the whole table. To compute step i you only look back two steps, so keep two variables and slide them forward:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev2, prev1 = 1, 2          # ways(1), ways(2)
        for _ in range(3, n + 1):
            prev2, prev1 = prev1, prev1 + prev2
        return prev1

The same shape in C#, for when the interview is on the .NET side:

public 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 current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

Trace n = 5 by hand and it stays honest: 1, 2, 3, 5, 8. Eight ways up a five-step staircase. O(n) time, O(1) space, no allocation, no recursion. This is the one I would leave in the codebase.

When each version earns its place

The four solutions are not a ranking where the last one always wins. They are a ladder of tradeoffs, and which rung you stop on depends on what you are optimising for.

Approach	Time	Space	Why you'd pick it
Plain recursion	O(2^n)	O(n)	Never — but it's the clearest statement of the recurrence
Top-down + memo	O(n)	O(n)	When the recurrence is complex and you think top-down
Bottom-up array	O(n)	O(n)	When you need the whole table later (reconstruction)
Two rolling vars	O(n)	O(1)	The default for a fixed-window recurrence

The array version is worth keeping in your head for a real reason: some problems ask you to reconstruct the path, not just count it, and then you need every cell, not just the last two.

The pattern, not the problem

Climbing Stairs is not worth remembering for its own sake. What is worth keeping is the shape it teaches: the answer at state n is built from a bounded window of earlier answers. The moment a problem fits that sentence, you reach for a rolling-variable DP and you are usually done.

You meet the same skeleton again with one extra twist each time:

• Min Cost Climbing Stairs (746) — same recurrence, but you minimise a cost instead of counting.
• House Robber (198) — dp[i] = max(dp[i-1], dp[i-2] + nums[i]); the window is identical, the operation changes.
• Decode Ways (91) — still "ways to reach position n", but the transitions depend on the characters, so some steps are blocked.

The keyword that gives it away is almost always "how many ways" or "minimum cost to reach", paired with a constraint small enough that an O(n) pass is plenty.

If you keep one instinct from this problem, make it this: when the answer at n depends on a fixed number of earlier answers, you almost never need an array, and you never need recursion. Climbing Stairs is the cheapest place to build that reflex before the problems start fighting back.