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 (the code above only keeps the last two cells, but seeing the whole table makes the recurrence clear):

Complexity: one pass from 2 to n, constant work per step, only two variables carried forward → O(n) time, O(1) space. Since any correct algorithm must produce a result that depends on all n steps, O(n) time is optimal here.