Coins 1, 5, 6 and 9: where greedy gets change wrong and a DP table doesn't

Here are two small problems that go wrong in different ways, and one idea that'll fix both of them.

A recursion that repeats itself millions of times

How many ways are there to climb n stairs if you can go up one or two steps at a time? Your last step was either a single or a double, so we can write:

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

It's correct, and you can't use it. ways(30) makes 2,692,537 calls, and ways(40) makes 331,160,281 of them, though there are only 31 and 41 different arguments in those runs. All of the other calls are working out values that we've already got.

If we store a value the first time we compute it, the work drops to linear:

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

A shortcut that looks right

Say we've got to make 11 out of coins of 1, 5, 6 and 9, and we'd like to use as few of them as we can. Greedy takes the biggest coin that'll fit at each step, so it picks 9, then 1, then 1, which comes to three coins. You can do it with two, though, since 5 + 6 is 11.

The trouble with greedy is that it commits too early. The 9 looked like the best choice, and it left us with 2, which we can only pay in ones. A DP table doesn't commit to anything until it has to. It works out the fewest coins for all of the smaller amounts first, and only then does it decide which coin it'll use last.

def fewest_coins(coins, amount):
    best = [0] + [float('inf')] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                best[a] = min(best[a], best[a - c] + 1)
    return best[amount]

Here's the table once it's filled in for coins of 1, 5, 6 and 9:

Amount	Fewest coins	One way to make it
1	1	1
2	2	1 + 1
3	3	1 + 1 + 1
4	4	1 + 1 + 1 + 1
5	1	5
6	1	6
7	2	6 + 1
8	3	6 + 1 + 1
9	1	9
10	2	9 + 1
11	2	6 + 5

A row only reads rows above it, and those are already final. For 11, the last coin could be 1, 5, 6 or 9, which would leave 10, 6, 5 or 2. If you add the last coin back in, those come to 3, 2, 2 and 3 coins, so the answer's 2.

Three questions before you write any DP

1. What's a state? It's the smallest description of a subproblem that you can get away with, and here it's an amount. If you leave something out, the answer isn't fixed by the state, and if you put too much in, the table gets far too big.
2. What's the last decision? For us it's the last coin. The recurrence tries all of the options and adds the best answer for what's left.
3. In what order do the entries become final? You'd like to fill the table so that anything an entry reads has already been worked out. Here that means going up through the amounts.

The cost is the number of states times the number of options. That's 11 × 4 for our example, or amount × len(coins) in general.

When I've got a DP solution that comes out wrong, I look at the state first. More often than not, it's left out something that the rest of the problem depends on.

You can watch the table fill in one step at a time on the original: https://geodesicpartners.co.uk/coding-dynamic-programming-why