Climbing Stairs: From Exponential Recursion to O(1) Space DP

"You can climb one or two steps at a time. In how many distinct ways can you reach the top of n stairs?" It is usually the first dynamic programming problem anyone meets, and it is worth doing slowly, because every idea in DP shows up here in miniature: a recurrence, overlapping subproblems, a table, and the observation that most of the table can be thrown away.

The problem it solves

Count the ordered sequences of moves, each move 1 or 2, whose sum is exactly n. For n = 4 there are five: 1111, 112, 121, 211 and 22. Order matters, so 112 and 211 are different climbs.

Listing the sequences works for tiny n and then collapses, because the count itself grows exponentially. The question is how to count them without listing them.

The intuition

Look at the last move instead of the first. Whatever climb ends on step n, its final move was either a single step from n - 1 or a double step from n - 2. Those two groups do not overlap, and together they cover every climb. So:

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

The base cases are ways(0) = 1, the empty climb, and ways(1) = 1. The sequence runs 1, 1, 2, 3, 5, 8, 13: Fibonacci, shifted by one place, so ways(n) is the Fibonacci number F(n + 1).

The recurrence alone is not the win. Written as plain recursion, ways(5) asks for ways(4) and ways(3), and ways(4) asks for ways(3) again. The same subproblem is solved over and over. That repetition, overlapping subproblems, is exactly what DP removes: solve each step once, remember it, reuse it.

Watch it run

The animation lays the staircase out as one row of cells, one per step. It fills ways(0) and ways(1) first, then builds each new cell from the two to its left, 1 + 1 = 2, 2 + 1 = 3, up to climb(5) = 8. The last frame greys out everything except the final two cells, which is the whole argument for the constant-space version.

The code

The direct recursion, with a counter to show what it costs:

calls = 0

def ways_naive(n):
    global calls
    calls += 1
    if n <= 1:
        return 1                         # step 0: stay put; step 1: one way
    return ways_naive(n - 1) + ways_naive(n - 2)

for n in [10, 20, 25]:
    calls = 0
    print(n, ways_naive(n), calls)
# 10 89 177
# 20 10946 21891
# 25 121393 242785

Three ways to remove the repetition. Memoisation keeps the recursive shape; the table fills the same values bottom-up; the rolling pair keeps only what the next step reads:

from functools import lru_cache

@lru_cache(maxsize=None)
def ways_memo(n):
    if n <= 1:
        return 1
    return ways_memo(n - 1) + ways_memo(n - 2)

def ways_table(n):
    dp = [1, 1] + [0] * (n - 1)          # dp[i] = ways to stand on step i
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def climb(n):
    a, b = 1, 1                          # ways(i - 1), ways(i)
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print([climb(n) for n in range(8)])      # [1, 1, 2, 3, 5, 8, 13, 21]
print(ways_memo(90) == ways_table(90) == climb(90))   # True

The follow-up interviewers like: allow any set of step sizes. The last-move argument still holds, it just has more cases, one per allowed size:

def climb_steps(n, steps):
    """Ways to reach step n when each move is one of `steps`."""
    dp = [1] + [0] * n
    for i in range(1, n + 1):
        dp[i] = sum(dp[i - s] for s in steps if s <= i)
    return dp[n]

print(climb_steps(5, [1, 2]), climb_steps(5, [1, 2, 3]), climb_steps(7, [2, 5]))
# 8 13 2

Both functions against a brute force that literally enumerates every sequence of moves, on 300 random staircases and step sets:

import itertools, random

def brute(n, steps):
    """Enumerate every sequence of moves and keep the ones that land on n."""
    total = 0
    for length in range(n + 1):
        for seq in itertools.product(steps, repeat=length):
            total += sum(seq) == n
    return total

random.seed(14)
ok = True
for _ in range(300):
    n = random.randint(0, 10)
    steps = sorted(random.sample(range(1, 5), random.randint(1, 3)))
    ok &= climb_steps(n, steps) == brute(n, steps)
    ok &= climb(n) == brute(n, [1, 2])
print(ok)                                # True

The complexity

• Plain recursion makes 2 * ways(n) - 1 calls, which the counts above confirm: 242,785 calls for n = 25. That grows like the Fibonacci numbers themselves, roughly by a factor of 1.618 per extra step.
• Memoised recursion computes each of ways(0) to ways(n) once, so it makes n + 1 distinct computations: O(n) time and O(n) space, plus a recursion depth of about n. Under CPython's default recursion limit of 1,000, ways_memo(1000) raises RecursionError.
• The table is O(n) time and O(n) space with no recursion at all.
• The rolling pair is O(n) time and O(1) space. Each step reads only the two previous values, so nothing older needs to be kept.
• Any step set of size k costs O(n * k) time with the table.

Where it goes wrong

• Wrong base case. Setting ways(0) = 0 breaks everything above it: ways(2) would come out as 1, missing the single double-step. The empty climb is one way to be on step zero.
• Counting combinations instead of orders. If the question says 1 + 2 and 2 + 1 are the same climb, the recurrence changes; that is the coin change ways problem, where the loop over step sizes goes outside the loop over amounts.
• Overflow in fixed-width languages. Python integers grow without limit, but a signed 64-bit integer holds climb(91) and not climb(92); the check climb(92) <= 2**63 - 1 prints False. Problems that go further usually ask for the answer modulo a prime.
• Updating the pair in the wrong order. a = b followed by b = a + b reads the new a. Python's tuple assignment, a, b = b, a + b, evaluates the right side first, which is why it is correct.

How to say it in an interview

"The last move onto step n came from n - 1 or from n - 2, and those cases don't overlap, so ways(n) = ways(n - 1) + ways(n - 2) with ways(0) = ways(1) = 1. Naive recursion is exponential because it recomputes the same steps. Filling the values bottom-up is O(n), and since each value only needs the previous two, I keep two variables and get O(1) space. If the allowed step sizes change, the same argument gives a sum over the allowed sizes."

The same shape, where each cell looks back a fixed distance, drives house robber, and the general move from recursion to a table is laid out in top-down vs bottom-up.