A problem where the obvious way fails
You have coins worth 1, 3 and 4. What is the fewest coins that make 6?
The obvious method is to take the biggest coin that fits, again and again. That is called a greedy method.
- Take a 4. 2 is left.
- Take a 1. 1 is left.
- Take a 1. Done. Three coins.
But 3 + 3 makes 6 with two coins. Grabbing the biggest coin first was a mistake that could not be undone.
To be sure of the best answer, every choice has to be considered. Doing that naively is far too slow. Dynamic programming is the way to consider every choice without repeating work.
The idea
Think about the last coin in the best answer for 6. It is a 1, a 3 or a 4.
- If it is a 1, the rest of the coins make 5, and they must be the best way to make 5.
- If it is a 3, the rest make 3, in the best way.
- If it is a 4, the rest make 2, in the best way.
So the answer for 6 is: 1 + the smallest of the answers for 5, 3 and 2.
The big problem has been written in terms of smaller versions of itself. And those smaller answers are needed again and again: the answer for 2 is used by 3, by 5 and by 6. Work each one out once, write it in a table, and look it up after that.
Filling the table
Start from 0 and work upwards. By the time you reach an amount, everything it needs is already in the table.
Amount (above) and the fewest coins to make it (in the box)
Violet: the amount being solved. Mint: the earlier answers it looks up.
Start. Coins of 1, 3, 4. The table will hold the fewest coins for every amount from 0 to 10. Making 0 takes 0 coins: that is the starting point.
- Amounts solved
- 1 / 11
- Working on
- 0
Each entry took at most three lookups, one per coin. The whole table for amounts up to 10 took 25 lookups.
def fewest_coins(coins, target):
best = [0] + [float("inf")] * target
for amount in range(1, target + 1):
for coin in coins:
if coin <= amount:
best[amount] = min(best[amount], best[amount - coin] + 1)
return best[target]Example
Reading the table
With coins 1, 3 and 4, the table for 0 to 10 is:
0 1 2 1 1 2 2 2 2 3 3
Amount 6 shows 2 (that is 3 + 3). Amount 10 shows 3 (that is 3 + 3 + 4). The greedy method would have given 4 + 4 + 1 + 1, which is four coins.
Why not just try everything?
Trying every combination directly means a tree of choices: three branches for the first coin, three for the next, and so on. The same amounts appear all over that tree and are worked out again each time. For a large target the tree has billions of branches.
The table has one entry per amount. For a target of 1,000 and three coins, that is 3,000 steps.
This is the same saving as in Recursion and Memoization. That lesson starts at the top and remembers answers on the way down. This one starts at the bottom and fills a table on the way up. They are two styles of the same technique.
| Top-down (memoization) | Bottom-up (table) | |
|---|---|---|
| How | Recursive function with a cache | Loop that fills an array |
| Works out | Only the entries that are needed | Every entry up to the target |
| Risk | Deep recursion can overflow the stack | None |
| Often easier to | Write first | Make fast and small |
When does it apply?
Two things must be true.
- The best answer is built from best answers to smaller versions. The best way to make 6 contains the best way to make 3.
- The smaller versions repeat. If each one were needed only once, there would be nothing to save.
A recipe
Say exactly what one table entry means
Here:
best[a]is the fewest coins that make amounta. Most of the difficulty is in this step.Write an entry in terms of smaller entries
best[a] = 1 + min(best[a - coin])over every coin that fits.Fill in the smallest cases by hand
best[0] = 0.Choose an order so that what you need is already there
Smallest amount first.
Read off the answer
best[target].
Other problems with the same shape
- Ways to climb stairs taking 1 or 2 steps at a time: ways(n) = ways(n − 1) + ways(n − 2).
- Longest common subsequence of two strings, which is how
difftools find what changed between two files. - Edit distance: the fewest single-letter changes to turn one word into another. Spell checkers use it.
- Knapsack: the most valuable set of items that fits a weight limit.
- Cheapest path through a grid moving only right or down.
They look unrelated. Each one is a table where an entry depends on a few earlier entries.
Key takeaways
- Taking the best-looking choice at each step can give the wrong answer: coins 1, 3, 4 and a target of 6.
- Dynamic programming writes the answer in terms of answers to smaller versions of the same problem.
- Each smaller answer is worked out once and stored, then looked up.
- It applies when best answers are built from smaller best answers, and those smaller problems repeat.
- The hard part is deciding what a table entry means. The rest follows.