Understanding the problem

Lesson · 8 min read · Dynamic programming

A recursion that repeats itself

How many ways are there to climb n stairs taking one or two steps at a time? The last step was either a single or a double, so ways(n) = ways(n − 1) + ways(n − 2). The recursion is correct, and written directly it is hopeless:

def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

ways(30) calls ways(28) twice, ways(27) three times, ways(26) five times, and so on up the Fibonacci numbers.

n	Calls made	Different arguments
30	2,692,537	31
40	331,160,281	41

Hundreds of millions of calls to evaluate 41 distinct values. The cure is to compute each value once and store it: either memoise the recursion, or fill a table from the bottom up. Either way the work drops from exponential to linear.

Why taking the best step now is not enough

Some problems tempt you to skip the table and just make the obviously best move at each step. Making change is the classic trap. With coins 1, 5, 6 and 9, the greedy way to make 11 takes the largest coin that fits each time: 9, then 1, then 1, three coins. But 5 + 6 makes 11 with two.

Greedy fails because a choice that looks best now can leave a remainder that is expensive later. Dynamic programming avoids the trap by never committing early: it works out the best answer for every smaller amount first, and only then asks which last coin to use.

Fewest coins for every amount up to 11 with coins 1, 5, 6 and 9. Each entry reads earlier entries that are already final.

Step 1 / 12

best
00∞1∞2∞3∞4∞5∞6∞7∞8∞9∞10∞11
amount0
best[a] will hold the fewest coins that make a. Amount 0 needs none; everything else starts unknown. Coins: 1, 5, 6, 9.
Step 2 / 12

best
0011∞2∞3∞4∞5∞6∞7∞8∞9∞10∞11
amount1best[a]1
Amount 1: the last coin is one of 1. Options: best[0] + 1 = 1. The smallest is 1, using a 1 last.
Step 3 / 12

best
001122∞3∞4∞5∞6∞7∞8∞9∞10∞11
amount2best[a]2
Amount 2: the last coin is one of 1. Options: best[1] + 1 = 2. The smallest is 2, using a 1 last.
Step 4 / 12

best
00112233∞4∞5∞6∞7∞8∞9∞10∞11
amount3best[a]3
Amount 3: the last coin is one of 1. Options: best[2] + 1 = 3. The smallest is 3, using a 1 last.
Step 5 / 12

best
0011223344∞5∞6∞7∞8∞9∞10∞11
amount4best[a]4
Amount 4: the last coin is one of 1. Options: best[3] + 1 = 4. The smallest is 4, using a 1 last.
Step 6 / 12

best
001122334415∞6∞7∞8∞9∞10∞11
amount5best[a]1
Amount 5: the last coin is one of 1, 5. Options: best[4] + 1 = 5, best[0] + 1 = 1. The smallest is 1, using a 5 last.
Step 7 / 12

best
00112233441516∞7∞8∞9∞10∞11
amount6best[a]1
Amount 6: the last coin is one of 1, 5, 6. Options: best[5] + 1 = 2, best[1] + 1 = 2, best[0] + 1 = 1. The smallest is 1, using a 6 last.
Step 8 / 12

best
0011223344151627∞8∞9∞10∞11
amount7best[a]2
Amount 7: the last coin is one of 1, 5, 6. Options: best[6] + 1 = 2, best[2] + 1 = 3, best[1] + 1 = 2. The smallest is 2, using a 1 last.
Step 9 / 12

best
001122334415162738∞9∞10∞11
amount8best[a]3
Amount 8: the last coin is one of 1, 5, 6. Options: best[7] + 1 = 3, best[3] + 1 = 4, best[2] + 1 = 3. The smallest is 3, using a 1 last.
Step 10 / 12

best
00112233441516273819∞10∞11
amount9best[a]1
Amount 9: the last coin is one of 1, 5, 6, 9. Options: best[8] + 1 = 4, best[4] + 1 = 5, best[3] + 1 = 4, best[0] + 1 = 1. The smallest is 1, using a 9 last.
Step 11 / 12

best
00112233441516273819210∞11
amount10best[a]2
Amount 10: the last coin is one of 1, 5, 6, 9. Options: best[9] + 1 = 2, best[5] + 1 = 2, best[4] + 1 = 5, best[1] + 1 = 2. The smallest is 2, using a 1 last.
Step 12 / 12

best
00112233441516273819210211
amount11best[a]2
Amount 11: the last coin is one of 1, 5, 6, 9. Options: best[10] + 1 = 3, best[6] + 1 = 2, best[5] + 1 = 2, best[2] + 1 = 3. The smallest is 2, using a 5 last.

Designing a table, in three questions

What is a state? The smallest description of a subproblem: here, an amount. Too little and the answer is not determined; too much and the table explodes.
What is the last decision? Here, the last coin. The recurrence tries every option for it and adds the best answer for what is left.
In what order are states final? Fill so that everything an entry reads is already computed: increasing amounts here.

The cost is the number of states times the options per state: 11 × 4 here, or amount × coins in general.

Say the three answers out loud before writing code. Interviewers ask for them, and most wrong DP solutions come from a state that forgot something the future depends on.