AI Hints
Home›DSA in Python Tutorial›Dynamic Programming
DSA in Python · Lesson 92 of 132

Practice: Coin Change

Fewest coins, done right.

⏱ 2 min read▶ Video at 1:49:54🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: Coin Change
From the video: Practice: Coin Change
  • 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.

coin_change.pypython
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")
Output
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.

keyvalue
Greedyone choice, no regrets
DPevery choice, reused answers
CostO(amount × coins)
Safe betwhen 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
Next up: Longest Common Subsequence — a two dimensional table