Practice: Coin Change
Fewest coins, done right.
Remember the strange coins, one, three, and four, where greedy failed to make six? Let's solve it properly. For every amount, from zero up, work out the fewest coins needed.

- Greedy failed
- Solve it properly
- Every amount from zero up
A table of best answers
Best of zero is zero coins. For each amount, we try every coin. If we use a coin worth C, we need one coin, plus the best answer for the amount minus C, which we've already worked out. We keep the smallest. Run it. Six needs just two coins, the right answer. And seven needs two, three and four.
def fewest_coins(amount, coins):
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]
for amount in [6, 7, 10]:
print(amount, "->", fewest_coins(amount, [1, 3, 4]), "coins")6 -> 2 coins 7 -> 2 coins 10 -> 3 coins
Greedy versus DP
Greedy made one choice at each step, and never reconsidered. Dynamic programming considers every choice, but reuses the answers to smaller amounts, so it stays fast. This takes O of amount times the number of coins. When greedy might fail, dynamic programming is the safe bet.
| key | value |
|---|---|
| Greedy | one choice, no regrets |
| DP | every choice, reused answers |
| Cost | O(amount × coins) |
| Safe bet | when greedy might fail |
Summary
Coin change builds the best answer for every amount, using answers to smaller amounts. It gets the strange coins right. Next, comparing two strings with a table.
Key takeaways- best[a] = min(best[a-c] + 1)
- Try every coin
- Always correct