Making change with the fewest coins

A cashier has to pay out an amount n using coins of given denominations, with as many coins of each kind as needed. The goal is to use as few coins as possible. With the coins 1, 4, 6 and 10, the amount 12 can be paid as 10 + 1 + 1 (three coins), as 4 + 4 + 4 (three coins) or as 6 + 6 (two coins); the answer is 2.

The page offers two coin systems, the US coins [1, 5, 10, 25] and the made-up system [1, 4, 6, 10]. Type an amount from 0 to 30 in the text field and press one of the four buttons. Change Recursive (capped at 25, because it is so slow), Change Memoized and Change Table are three versions of the same dynamic programming idea; Change Greedy shows the simple rule a person would use, which is not always right.

The greedy rule and why it fails

The obvious strategy is greedy: keep taking the largest coin that still fits. For the US coins this always gives the fewest coins (for every amount on this page it agrees with the table version). For [1, 4, 6, 10] it does not: for 8 greedy takes 6 + 1 + 1 (3 coins) but 4 + 4 needs only 2, and for 12 greedy takes 10 + 1 + 1 while 6 + 6 is better. The textbook example is the coins {1, 3, 4} and the amount 6: greedy pays 4 + 1 + 1, the best is 3 + 3. Taking a big coin early can force many small coins later, and greedy never reconsiders. Coin systems for which greedy is always optimal are called canonical; most real currencies are designed to be canonical, but a program cannot assume it.

Paying 12 with coins 1, 4, 6, 10: greedy takes 10, 1, 1 for 3 coins, which is not the fewest; the best answer is 6 and 6, 2 coins
Greedy grabs the 10 first and is stuck with two 1s; dynamic programming finds 6 + 6.

The recurrence

Think about the last coin in a best solution for amount n. It is one of the coins c ≤ n. Whatever it is, the other coins pay n − c, and they must do so with the fewest possible coins: if they didn't, we could swap in a better way to pay n − c and get a better solution for n. This is optimal substructure. We don't know which coin is last, so we try them all. Writing C[n] for the fewest coins that pay n:

C[0] = 0                                            (nothing to pay: no coins)
C[n] = 1 + min { C[n - c] : c is a coin and c <= n }    for n > 0
Table C for amounts 0 to 12 with coins 1, 4, 6, 10: C[12] looks back at C[11]=2, C[8]=2, C[6]=1 and C[2]=2; the candidates 1 + those are 3, 3, 2, 3, so the smallest is via coin 6 and C[12] = 2
Each table entry looks back one coin's width for every coin and keeps the cheapest: C[12] = 1 + C[6] = 2.

Version 1: plain recursion (Change Recursive)

The recurrence translates straight into the code shown on the canvas (it uses -1 to mean "no answer yet"; the loop assumes the coins are sorted from small to large):

def change(n, coinArray):
    if (n == 0):
        return 0
    best = -1
    for coin in coinArray:
        if (coin <= n):
            nextTry = change(n - coin, coinArray)
            if (best < 0 or best > nextTry + 1):
                best = nextTry + 1
    return best

This is correct but hopelessly slow, because the same subproblems are solved again and again (overlapping subproblems). change(12) with [1, 4, 6, 10] calls change(11), change(8), change(6) and change(2); change(11) in turn calls change(10) and change(7), and both of those end up calling change(6) again, and so on. There are only 13 different amounts from 0 to 12, yet the recursion makes 149 calls. For 20 it makes 3,409 calls and for 25 it makes 24,165, although only 26 different amounts exist. The number of calls T(n) = 1 + T(n−1) + T(n−4) + T(n−6) + T(n−10) (for n ≥ 10) grows exponentially in n, just like the naive Fibonacci recursion. On the canvas each call appears as a line change(v, [...]), indented one step per level of recursion, and is replaced by its answer and the coins used when it returns.

Version 2: memoization (Change Memoized)

The fix is to remember every answer. Keep an array C filled with -1 ("unknown"). Before doing any work, a call looks up its amount; if the answer is already there it returns it at once, otherwise it computes it with the same loop as before and stores it:

def changeMem(n, coinArray, C):          # C[v] == -1 means "not computed yet"
    if (C[n] >= 0):
        return C[n]                      # memo hit: no recursion at all
    if (n == 0):
        best = 0
    else:
        best = -1
        for coin in coinArray:
            if (coin <= n):
                nextTry = changeMem(n - coin, coinArray, C)
                if (best < 0 or best > nextTry + 1):
                    best = nextTry + 1
    C[n] = best
    return best

Now each amount is computed only once; every later request is a single lookup. changeMem(6) with [1, 4, 6, 10] goes straight down the chain 6 → 5 → 4 → 3 → 2 → 1 → 0 (always trying coin 1 first), and on the way back up every other coin is a memo hit: change(4) finds C[0] = 0, change(5) finds C[1] = 1, change(6) finds C[2] = 2 and C[0] = 0. For 12 the total drops from 149 calls to 32 (13 real computations plus 19 lookups). On the canvas the two columns on the right fill in as calls return, and a cell flashes when it is looked up.

Version 3: bottom-up table (Change Table)

Since C[n] only depends on smaller amounts, we can skip the recursion and simply fill the table from 0 upwards. A second array coinUsed remembers which coin gave the minimum, so the actual coins can be recovered afterwards:

def changeTable(n, coinArray):
    C[0] = 0
    for v in 1 .. n:
        C[v] = -1
        for coin in coinArray:
            if (coin <= v) and (C[v] < 0 or C[v] > C[v - coin] + 1):
                C[v] = C[v - coin] + 1
                coinUsed[v] = coin
    # recover the coins: repeatedly pay coinUsed[v]
    v = n
    while v > 0:
        output coinUsed[v]
        v = v - coinUsed[v]
    return C[n]

On the canvas the left column, # of Coins Required, is C and the right column, Coins to Use, is coinUsed; the blue numbers are the amounts. While a cell is being filled, it and the cell C[v - coin] it reads are highlighted. At the end the answer change(n) = ... appears at the top, and the coins of the solution fly out of the Coins to Use column one by one.

Worked example: coins [1, 4, 6, 10], amount 12

Each row lists the candidates 1 + C[v - coin] for every coin that fits; the smallest wins. When two coins tie, the page keeps the first (smallest) coin, because it only replaces the current best when the new value is strictly smaller.

 v   candidates  1 + C[v - coin]                              C[v]  coinUsed[v]
 0   (base case)                                                0     -
 1   coin 1: 1+C[0]=1                                           1     1
 2   coin 1: 1+C[1]=2                                           2     1
 3   coin 1: 1+C[2]=3                                           3     1
 4   coin 1: 1+C[3]=4   coin 4: 1+C[0]=1                        1     4
 5   coin 1: 1+C[4]=2   coin 4: 1+C[1]=2                        2     1
 6   coin 1: 1+C[5]=3   coin 4: 1+C[2]=3   coin 6: 1+C[0]=1     1     6
 7   coin 1: 1+C[6]=2   coin 4: 1+C[3]=4   coin 6: 1+C[1]=2     2     1
 8   coin 1: 1+C[7]=3   coin 4: 1+C[4]=2   coin 6: 1+C[2]=3     2     4
 9   coin 1: 1+C[8]=3   coin 4: 1+C[5]=3   coin 6: 1+C[3]=4     3     1
10   coin 1: 1+C[9]=4   coin 4: 1+C[6]=2   coin 6: 1+C[4]=2
     coin 10: 1+C[0]=1                                          1     10
11   coin 1: 1+C[10]=2  coin 4: 1+C[7]=3   coin 6: 1+C[5]=3
     coin 10: 1+C[1]=2                                          2     1
12   coin 1: 1+C[11]=3  coin 4: 1+C[8]=3   coin 6: 1+C[6]=2
     coin 10: 1+C[2]=3                                          2     6

So C[12] = 2. To find the coins, follow coinUsed: coinUsed[12] = 6, leaving 12 − 6 = 6; coinUsed[6] = 6, leaving 0. The solution is 6 + 6. The greedy button on the same input pays 10 + 1 + 1 = 3 coins. Try 8 as well: the table gives 4 + 4, greedy gives 6 + 1 + 1.

Why it is correct

By induction on n. C[0] = 0 is clearly right. For n > 0, suppose all smaller entries are right. Any way of paying n ends with some coin c, and uses at least 1 + C[n − c] coins, so it can't beat the minimum over all c. Conversely, the coin that attains the minimum plus an optimal way to pay n − c is a real solution with exactly that many coins. So the minimum is achieved and nothing does better. All three versions compute exactly this recurrence; they differ only in the order in which the values get computed and in whether they are remembered.

Running time and space

  • Plain recursion: exponential time in n (see the call counts above), recursion depth up to n (a chain of 1-coins), so O(n) stack space.
  • Memoized: each of the n + 1 amounts is computed once, looping over k coins, so Θ(nk) time, Θ(n) for the memo and up to n nested calls on the stack.
  • Table: Θ(nk) time, Θ(n) space, no recursion. Recovering the coins takes O(C[n]) more steps.

Like knapsack, Θ(nk) is pseudo-polynomial: it is polynomial in the value of n, not in the number of digits needed to write it down.

Common mistakes, edge cases and variants

  • Base case: C[0] = 0, not 1. Paying nothing takes zero coins.
  • Unreachable amounts: without a 1-coin some amounts can't be paid at all (coins {4, 6} can't pay 7). A general version needs a value such as infinity (or -1) for "impossible" and must skip such subproblems instead of adding 1 to them. Both coin sets on this page contain 1, so every amount is reachable.
  • Sorted coins: the page's recursion stops the loop at the first coin that is too large, which is only right if the coins are sorted in increasing order.
  • Trusting greedy: it is correct only for canonical coin systems, as the [1, 4, 6, 10] example shows.
  • Counting ways instead: "how many different ways can I pay n?" is a different question with a similar table. There the loop over coins must be the outer loop, otherwise 1 + 4 and 4 + 1 are counted as two ways. See the Coin Change (number of ways) page.
  • Limited coins: if each coin may be used only once, the problem becomes a variant of the 0/1 knapsack and needs a two-dimensional table (see Knapsack). The unlimited version here is a special case of the unbounded knapsack.

Where it is used

Cash registers and vending machines use greedy because real currencies are canonical, but the dynamic programming version is what you need for arbitrary denominations, for stamps, for packing standard sizes (cutting a length of cable from stock pieces), and for any "fewest steps to reach a total" puzzle. More importantly, it is one of the clearest examples of the three ways to evaluate a recurrence — plain recursion, memoization and bottom-up tabulation — which appear throughout dynamic programming, from Fibonacci numbers to sequence alignment.