Pointer Walk

Dynamic Programming

Fewest coins to make an amount. The greedy answer is wrong, the brute-force answer is slow, and a small table gets it right.

AlgorithmsIntermediate11 min read

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.

Fewest coins, using 1, 3, 4Interactive

Amount (above) and the fewest coins to make it (in the box)

00
1
2
3
4
5
6
7
8
9
10

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.

python
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)
HowRecursive function with a cacheLoop that fills an array
Works outOnly the entries that are neededEvery entry up to the target
RiskDeep recursion can overflow the stackNone
Often easier toWrite firstMake fast and small

When does it apply?

Two things must be true.

  1. The best answer is built from best answers to smaller versions. The best way to make 6 contains the best way to make 3.
  2. The smaller versions repeat. If each one were needed only once, there would be nothing to save.

A recipe

  1. Say exactly what one table entry means

    Here: best[a] is the fewest coins that make amount a. Most of the difficulty is in this step.

  2. Write an entry in terms of smaller entries

    best[a] = 1 + min(best[a - coin]) over every coin that fits.

  3. Fill in the smallest cases by hand

    best[0] = 0.

  4. Choose an order so that what you need is already there

    Smallest amount first.

  5. 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 diff tools 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    9 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress