The coin change problem

A cashier making change grabs the biggest coin that fits, then the next, and for euros or dollars that always gives the fewest coins. Change the coins to 1, 3 and 4, though, and the same habit pays 6 with three coins when two would do. Dynamic programming finds the true minimum for any coins.

A row of amounts, each with the fewest coins that make it, above coins of three different sizes
A row of amounts, each with the fewest coins that make it, above coins of three different sizes

Two questions

The coin change problem comes in two flavours. The first asks for the fewest coins that make an exact amount; it is also called the change-making problem. The second asks how many different combinations of coins make it. In both, every kind of coin may be used as often as you like, and both are solved by building the answer for every amount from the answers for smaller amounts.

Fewest coins, step by step

Make a row of cells for the amounts from 0 up to the target. Amount 0 takes 0 coins; every other amount starts at infinity. Go through the amounts in order, and for each one try every coin c that fits: the cell for the amount minus c, plus one coin, is a candidate. Keep the smallest. Each cell depends only on cells to its left, which are already final, so one pass fills the row.

An example

With coins 1, 3 and 4: amount 1 takes 1 coin, 2 takes 2, 3 takes 1 (a single 3) and 4 takes 1. For 5, try 1 (4 needs 1, so 2 coins), 3 (2 needs 2, so 3 coins) and 4 (1 needs 1, so 2 coins): the best is 2. For 6, try 1 (5 needs 2, so 3), 3 (3 needs 1, so 2) and 4 (2 needs 2, so 3): the best is 2, by 3 + 3. Greedy would have paid 4 + 1 + 1.

Counting the ways

To count combinations, add the coins one at a time. With only the first coin, each amount can be made in one way or not at all. When a new coin c joins, the ways to make an amount a are the old ways, without c, plus the ways to make a − c with c allowed again, because each of those becomes a way to make a by adding one more c. With coins 1, 2 and 5 there are 4 ways to make 5: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 and 1 + 1 + 1 + 1 + 1.

When greedy is enough

A coin system for which greedy always gives the fewest coins is called canonical. Most modern currencies are designed that way, and in 1994 David Pearson described a test that checks a coin system in a number of steps that grows only polynomially with the number of coins. The old British coins were not canonical: greedy pays 48 pence as a half crown, a shilling and a sixpence, where two florins would do.

Explore it

Open the app, switch to the Table view and press Step. In Fewest coins mode, the orange cell is the amount being worked out and the blue cell is the smaller amount the coin leaves; the row underneath keeps the last coin, and at the end the coins are read back along it. Switch to Number of ways and watch the counts grow row by row as each coin joins.

Frequently asked questions

Is the coin change problem a knapsack problem?

A close relative. The fewest coins version is an unbounded knapsack problem in which each coin is an item whose weight is its face value, the bag must be filled exactly, and the goal is the fewest items.

What is the time complexity?

O(k·A) for k kinds of coins and an amount A, in both versions. The table for the fewest coins has A + 1 cells, and the table for the ways (k + 1)·(A + 1), though one row is enough if the cells are updated in place.

Why count the coins in a fixed order?

If every amount tried every coin, 1 + 2 and 2 + 1 would be counted as two ways. Adding the coins one row at a time means a combination is always built from the earlier coins first, so each one is counted exactly once.

Can the coins be read back for the number of ways?

Not as a single answer, because there are many. The fewest coins version keeps the last coin of each amount, which is enough to rebuild one best combination.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try coin change