From memo to table: climbing stairs

The formula was total time = number of distinct subproblems × work per subproblem.

For memoized fib that was n subproblems at O(1) each, giving O(n), against the naive 2ⁿ.

Dynamic programming is that formula turned into a method. Identify the subproblems, find how each is built from smaller ones, then compute each exactly once.

The only real change from memoization is direction. Memoization starts at the answer and recurses down, and DP starts at the base cases and builds up, but the set of subproblems solved is identical.

This unit does it three times, on the three most-asked 1-D DP problems.

Climbing stairs

The interview classic. A staircase has n steps and you can climb 1 or 2 steps at a time, so how many distinct ways are there to reach the top?

The way in is to think about the last move onto step n. It came either from step n−1 as a 1-step, or from step n−2 as a 2-step.

Those two groups cover every possible way, and they cannot overlap, since the last move is either one size or the other. That is what makes adding them valid rather than double-counting.

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

with ways(1) = 1 and ways(2) = 2. An equation like that is called a recurrence, and this one is fib from unit 5 in a costume.

You already know one way to compute it quickly, which is recursion plus a memo. Dynamic programming 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, so nothing needs to be recomputed or remembered.

Top-down and bottom-up, side by side

Both compute the same recurrence.

def climb_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 2:
        return n
    memo[n] = climb_memo(n - 1, memo) + climb_memo(n - 2, memo)
    return memo[n]

def climb_table(n):
    if n <= 2:
        return n
    table = [0] * (n + 1)
    table[1], table[2] = 1, 2
    for i in range(3, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

print(climb_memo(10))
print(climb_table(10))
print(climb_table(45))

Output

89
89
1836311903

Same answers for n = 10, which is the point. The two functions solve the same set of subproblems and differ only in the order.

climb_memo recurses down from n and fills the memo on the way back up, the lesson 5-3 pattern.

climb_table walks i upward from 3, and it never checks whether an ingredient is ready, because the loop order guarantees it. Choosing that order correctly is the one skill bottom-up DP demands.

The table is sized n + 1 so that table[n] exists and indices match step numbers directly. Index 0 is unused here, which is cheaper than mental arithmetic on every access.

The table version cannot hit recursion limits, and that is its practical advantage. climb_memo(45) is fine, and climb_memo(5000) would raise RecursionError while climb_table(5000) would not.

Both are O(n) time and O(n) space, and the next block removes the space.

The O(1)-space follow-up

The follow-up interviewers reach for first is whether the table's O(n) memory is actually needed.

Read the recurrence again. Computing table[i] touches only table[i-1] and table[i-2], so everything older is dead weight the moment it has been used.

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, which covers climbing stairs, house robber, and fib.

It does not work when the recurrence can reach arbitrarily far. Coin change reads table[a - c] for every coin c, so an entry from far back can still be needed and the full table has to stay.

State the reach out loud before claiming the optimization. Naming the two cells you depend on is what makes the claim checkable instead of a guess.

Two variables instead of a table

a and b hold the previous two answers and slide forward.

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

print(climb(5))
print(climb(45))

Output

8
1836311903

a, b = 1, 2 seeds the pair with ways(1) and ways(2), and after every loop turn they hold ways(i−1) and ways(i).

The line a, b = b, a + b depends on Python evaluating the whole right side before assigning. Splitting it into two statements would overwrite a and corrupt the sum.

The loop runs n - 2 times because the first two answers are already in hand, and the loop variable is _ since the count is all that matters.

climb(45) still answers instantly with 1,836,311,903 ways, which is the same number climb_table(45) produced with a 46-element list.

The cost is now O(n) time and O(1) space, and the only thing given up is access to the intermediate values. If a problem asks which path was taken, the full table has to stay.

min_cost_climb

Each step has a cost, and the table holds the cheapest way to reach each position.

def min_cost_climb(cost):
    n = len(cost)
    table = [0] * (n + 1)
    for i in range(2, n + 1):
        table[i] = min(table[i - 1] + cost[i - 1],
                       table[i - 2] + cost[i - 2])
    return table[n]

print(min_cost_climb([10, 15, 20]))
print(min_cost_climb([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))

Output

15
6

The meaning of the table comes first: table[i] is the cheapest total cost to reach position i, which makes table[0] and table[1] both 0 since you may start on either step without paying to arrive.

The skeleton is climb_table with min(...) in place of +, because this problem optimizes rather than counts. That substitution is most of what separates a counting DP from an optimizing one.

Each entry considers exactly two ways to arrive, from i−1 or from i−2, and each pays the cost of the step being left rather than the one being entered.

The top is position n, one past the last step, which is why the table has n + 1 entries and the answer is table[n].

For [10, 15, 20] the answer is 15: start on step 1, pay 15, and jump two to the top, skipping both the 10 and the 20.

The second case totals 6 by paying every 1 and stepping over each 100, which is the kind of choice a greedy cheapest-next-step rule would get wrong.

The two ingredients are what table[i] means in words, and the recurrence that builds it from earlier entries.

The meaning comes first, phrased as a full sentence. "table[i] is the number of ways to reach step i" or "table[i] is the cheapest cost to reach position i".

Then the recurrence with its base cases, which is where the actual thinking happens. Getting the meaning right usually makes the recurrence obvious, and a vague meaning makes it impossible.

The base cases are part of the second sentence rather than an afterthought. They are the subproblems the recurrence cannot build, and mis-stating them is the most common source of off-by-one DP bugs.

If you can say both sentences, the code writes itself, and it is usually three or four lines. If you cannot, no amount of typing will save you.

This two-sentence discipline is the highest-value interview habit in this course, and it is worth saying out loud before writing anything.