From memo to table: climbing stairs

Climbing stairs

The interview classic: a staircase has n steps, and you can climb 1 or 2 steps at a time. How many distinct ways can you reach the top?

Think about the last move onto step n. It came from step n-1 (a 1-step) or from step n-2 (a 2-step). Those two groups cover every way, and they cannot overlap. So:

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

with ways(1) = 1 and ways(2) = 2. That equation is called a recurrence, and it is fib from unit 5 in a costume.

You already know one way to compute it fast: recursion + memo. Dynamic programming (DP) flips the direction: instead of starting at n and recursing down, fill a table from the bottom up. table[i] holds ways(i), and by the time you compute table[i], its two ingredients are already sitting in the table.

The O(1)-space follow-up

The follow-up interviewers reach for first: "your table costs O(n) memory — do you actually need it?" Read the recurrence again: computing table[i] touches only table[i-1] and table[i-2]. Everything older is dead weight. So keep just two variables and slide them forward — same computation, same answer, O(1) space.

This works whenever the recurrence has a fixed, short reach back (climbing stairs, house robber, fib). It does NOT work when the recurrence can reach arbitrarily far — coin change reads table[a - c] for every coin c — so state the reach out loud before claiming the optimization.