Coin change, done right
Time to settle the score from lesson 8-2: coins [1, 3, 4], amount 6, where greedy answered 3 and the truth was 2.
Meaning: table[a] = the fewest coins that make amount a. Recurrence: 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: table[0] = 0. Unreachable amounts stay at infinity (float("inf")).
Notice what DP is doing that greedy refused to do: it considers every coin as the last one, not just the biggest, and it reuses the already-computed best for each smaller amount. Cost: amounts × coins, O(amount · len(coins)).
Code exercise · python
Run this. The printed table is the whole story: table[6] becomes 2 via table[3] + one more 3-coin. The second call shows an impossible case: odd amounts stay inf with only even coins, so it returns -1.
Quiz
Greedy failed on coins [1, 3, 4] but this DP succeeds. What exactly does the DP do differently?
Code exercise · python
Your turn: count the COMBINATIONS instead. count_ways(amount, coins) = how many different multisets of coins make the amount (order does not matter: 1+3 and 3+1 are the same way). The loop order given in the comments makes each coin type considered once, which is what kills order-duplicates.
Quiz
count_ways puts coins in the OUTER loop and amounts inner. What would swapping the loops (amounts outer, coins inner) count instead?
Problem
For min_coins with amount = 100 and 4 coin types, how many table-update steps does the DP do, roughly? (amounts × coins)