Climbing Stairs

Directly translate the recurrence into recursive calls: from step i, branch into taking 1 step or 2 steps, and count how many branches land exactly on n.

class Solution:
    def climbStairs(self, n: int) -> int:
        def ways(i: int) -> int:
            if i > n:
                return 0
            if i == n:
                return 1
            return ways(i + 1) + ways(i + 2)
        return ways(0)

This is correct — it explores every possible sequence of 1s and 2s — but the same sub-calls get recomputed enormous numbers of times (ways(5) gets called from many different paths). The call tree doubles in size with every step, giving O(2ⁿ) time.

The brute force is only slow because it re-solves the same subproblems. Cache each ways(i) the first time it’s computed, and every repeat call becomes an O(1) lookup instead of a re-exploration.

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

Now there are only n distinct subproblems, each solved once in O(1) work (plus the two calls it spawns, each already memoized) → O(n) time. The memo dict and the recursion depth both cost O(n) space.

Flip the recursion around: build up from the base cases instead of recursing down from n. dp[i] = number of ways to reach step i, computed left to right as dp[i] = dp[i-1] + dp[i-2]. And since each step only ever needs the previous two values, there’s no need to store the whole array — two variables suffice.

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

Conceptually, here’s the full dp array being filled for n = 5, but the real point is that the code never stores this array — it just slides two variables along it. Watch the prev2 / prev1 chips advance one cell per step, reading the previous two values and writing a new one while dropping the oldest:

Complexity: one pass from 2 to n, constant work per step, only two variables carried forward → O(n) time, O(1) space.