Coin change, done right

Coin change, done right

Time to settle the score from lesson 8-2, where coins [1, 3, 4] and an amount of 6 had greedy answering 3 while the truth was 2.

Meaning first: table[a] is the fewest coins that make amount a.

Recurrence second. The last coin in an optimal payment is some coin c, and before it you had an optimal payment for a - c.

table[a] = 1 + min(table[a − c] for every coin c ≤ a)

Base case is table[0] = 0, since zero coins make zero. Unreachable amounts stay at infinity, written float("inf").

Notice what DP is doing that greedy refused to do. It considers every coin as the last one rather than just the biggest, and it reuses the already-computed best for each smaller amount.

The cost is amounts times coins, so O(amount · len(coins)). That is not strictly polynomial in the input size, since the amount is a value rather than a length, which is why very large amounts still need a different approach.

min_coins

The printed table is the whole story.

def min_coins(amount, coins):
    INF = float("inf")
    table = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and table[a - coin] + 1 < table[a]:
                table[a] = table[a - coin] + 1
    print(table)
    return table[amount] if table[amount] != INF else -1

print(min_coins(6, [1, 3, 4]))
print(min_coins(7, [2, 4]))

Output

[0, 1, 2, 1, 1, 2, 2]
2
[0, inf, 1, inf, 1, inf, 2, inf]
-1

table[6] becomes 2 through table[3] + 1, meaning one 3-coin on top of the optimal payment for 3. Greedy never considered 3 as the last coin because 4 fit.

Reading the first table across, table[2] is 2 from two pennies, table[3] and table[4] are both 1 from their own coins, and table[5] is 2 from 4 + 1.

The coin <= a guard prevents a negative index, and in Python a negative index would silently read from the end of the list rather than raising, which makes the guard a correctness requirement rather than a nicety.

Inner-loop entries are always ready when read, since a - coin is strictly less than a and the outer loop runs upward. That is the loop-order argument from lesson 9-1 again.

The second call shows an impossible case. With only even coins, every odd amount stays at infinity, and 7 returns −1 while the reachable even amounts get real answers.

The DP tries every coin as the last coin, for every amount, backed by optimal answers to all smaller amounts.

Greedy makes one irreversible choice per step and lives with it. The DP inner loop is a minimum over all possible last coins, so no candidate is skipped.

table[a - coin] is guaranteed optimal because it was filled earlier, which is what makes considering only the last coin sufficient. There is no need to look at whole payment sequences.

That property has a name worth knowing, optimal substructure: the best solution is built from best solutions to smaller instances. Coin change has it and greedy simply failed to exploit it.

Exhaustive choices plus reused subproblems equals DP, and both halves matter. Exhaustive alone is the exponential recursion from lesson 8-2, and reuse alone is meaningless without the choices.

That pairing is why DP handles the interaction effects that break greedy.

count_ways

Counting combinations rather than minimizing coins, where order does not matter.

def count_ways(amount, coins):
    table = [0] * (amount + 1)
    table[0] = 1
    for coin in coins:
        for a in range(coin, amount + 1):
            table[a] += table[a - coin]
    return table[amount]

print(count_ways(5, [1, 2, 5]))
print(count_ways(6, [1, 3, 4]))

Output

4
4

Here table[a] means the number of ways to make amount a using the coins considered so far, and table[0] = 1 because there is exactly one way to make nothing, namely take nothing.

The counting DP uses += where the optimizing DP used min. Same table shape, different combiner, and that is the general distinction between counting and optimizing problems.

Loop order is the crucial detail. Coins on the outside means all the 1s are decided before 2s exist, so each combination is built in one canonical order and counted once.

The inner range starts at coin rather than 1, which replaces the coin <= a guard, since amounts below the coin cannot use it.

The 4 ways to make 5 from {1, 2, 5} are 1+1+1+1+1, 1+1+1+2, 1+2+2, and 5.

Swapping the loops would count ordered sequences, so 1+3 and 3+1 would be two different ways.

With coins outer, the table finishes accounting for one coin type before the next one exists. Every combination is therefore built in one canonical order, non-decreasing by coin, and counted once.

With amounts outer, each amount treats every coin as a possible last step. That is the right structure for min_coins, where order is irrelevant to the answer, and it double-counts when the answer is a count.

The distinction has standard names. Combinations, which is coins outer, versus permutations or compositions, which is amounts outer, and problems ask for both.

So loop order is part of the table's meaning rather than a style choice. It is a classic hidden-test trap, because a small test where every coin is used at most once gives the same number either way.

The way to keep it straight is to state the meaning precisely. "Ways using only the first k coin types" forces coins outer, and "ways whose last coin is anything" forces amounts outer.

About 100 × 4 = 400 table-update steps.

The outer loop runs over 100 amounts and the inner loop over 4 coins, so each of the 100 cells does at most 4 comparisons.

Compare that with the exhaustive recursion from lesson 8-2, which branches 4 ways per level and revisits the same amounts through countless different paths.

The number of distinct paths to an amount grows exponentially, and the number of distinct amounts is 100. DP charges you for the second.

DP's price is proportional to the size of the table rather than the number of paths through it, and that is the entire trick.

It also tells you when DP stops helping. At an amount of 10¹² the table is too large to build, so the table size is the thing to estimate before committing to the approach.