Coin change

Coin change is the problem of paying an amount with coins of given values, with as many coins of each value as you like: pay it with the fewest coins, or count the ways to pay it. Both questions are solved by filling a table over the amounts from 0 up to the one you pay. If each coin can be used only once, see knapsack instead.

Explanation

A shop takes coins of 1 and 2, and you pay 4. The fewest coins is 2, two coins of 2. In a purse, 1 + 1 + 2 and 2 + 1 + 1 are the same coins, so they are one payment. There are three payments of 4: 1 + 1 + 1 + 1, 1 + 1 + 2 and 2 + 2.

Fig. 1. The three ways to pay 4 with coins of 1 and 2.

The fewest coins come from the table of the introduction to dynamic programming. Counting the payments needs a new idea. With coins of 1, 3 and 4, how many payments of 6 are there? For amount 100 there are already 451, far too many to list, so we want a table here too.

The fewest-coins rule from the introduction looks at the last coin: the fewest coins for 6 is 1 plus the smallest of the counts for 5, 3 and 2. The staircase in the introduction counts the ways to climb the steps by the same idea, adding instead of taking the smallest. Counting works the same way here: the last coin is 1, 3 or 4, so the count for 6 is the count for 5, plus the count for 3, plus the count for 2. Call this the sum rule. Paying 0 has one way, with no coins. Filled from 0 up, the row is 1, 1, 1, 2, 4, 6, 9, so the sum rule gives 9.

Now list the payments of 6: six coins of 1; a 3 and three 1s; two 3s; a 4 and two 1s, only 4 payments. The sum rule counts every order of the same coins separately: a 3 and three 1s in 4 orders, a 4 and two 1s in 3 orders, so the 4 payments give 1 + 4 + 1 + 3 = 9 (Fig. 2). It counts sequences of coins, where the order matters, just as the staircase counts sequences of steps.

Fig. 2. The sum rule counts 9 sequences, but they are only 4 payments: 3 + 1 + 1 + 1 is counted four times.

So build each payment in one fixed order: all the 1s first, then the 3s, then the 4s. In this order, a payment that uses 3s but no 4s always ends with a 3. So we can count in stages: first the payments that use only 1s, then those with 1s and 3s, then all three values. At each stage the new payments are exactly those that end with the new value. Any fixed order of the values works; it doesn't have to go from small to large.

With only coins of 1, every amount has one payment. Now let the 3s in. A payment of 6 either has no 3 (1 such payment, counted before) or ends with a 3. Before that 3 comes a payment of 3 with coins 1 and 3, and there are 2: three 1s, or one 3 (Fig. 3). So 6 has 1 + 2 = 3 payments with coins 1 and 3. Let the 4s in the same way: 3 payments with no 4, plus 1 payment of 2 before a last 4. So 6 has 3 + 1 = 4 payments, the same as the list.

Fig. 3. Every payment of 6 that uses a 3 is a payment of 3 followed by one more 3. The payment of 3 may contain a 3 itself.

Each payment is counted once, at the stage that lets in the last of its values, as a payment that ends with a coin of that value. The part before the last coin may contain the same value again, so a coin value can appear many times.

Coin change counts payments this way. Let's fill the whole table: one row for each coin value let in, and in each row the amounts from small to large.

No coins are let in yet. Paying 0 takes no coins, the empty payment, so amount 0 gets 1 and every other amount gets 0.

Coins of 1 are let in. Amount 0 is smaller than 1, so it copies 1 from the row above.

Amount 1: 0 payments without a 1, plus 1 payment of 0 before the last 1: 1.

Amount 2: 0 payments without a 1, plus 1 payment of 1 before the last 1: 1.

Amount 3: 0 + 1 = 1.

Amount 4: 0 + 1 = 1.

Amount 5: 0 + 1 = 1.

Amount 6: 0 + 1 = 1. With only 1s, every amount has one payment.

Coins of 3 are let in. Amounts 0, 1 and 2 are smaller than 3, so they copy 1, 1 and 1 from the row above.

Amount 3 with coins 1 and 3: 1 payment without a 3, plus 1 payment of 0 before the last 3: 2.

Amount 4: 1 payment without a 3, plus 1 payment of 1 before the last 3: 2.

Amount 5: 1 payment without a 3, plus 1 payment of 2 before the last 3: 2.

Amount 6: 1 payment without a 3, plus 2 payments of 3 before the last 3: 3.

Coins of 4 are let in. Amounts 0 to 3 are smaller than 4, so they copy 1, 1, 1 and 2 from the row above.

Amount 4 with coins 1, 3 and 4: 2 payments without a 4, plus 1 payment of 0 before the last 4: 3.

Amount 5: 2 payments without a 4, plus 1 payment of 1 before the last 4: 3.

Amount 6: 3 payments without a 4, plus 1 payment of 2 before the last 4: 4.

1/17

Fig. 4. Step through the table with the buttons or the arrow keys. Each new number is the cell above it (no coin of this value) plus the cell as many columns to the left as the coin is worth, in the same row (the payment ends with this coin).

The run counted more than amount 6: the last row holds the number of payments for every amount from 0 to 6.

Implementation

The counts go in a vector ways with one cell for each amount from 0 to S, the amount to pay. In the stage names of the introduction:

1. State: ways[x] is the number of payments of x with the coin values let in so far.

2. Base case: ways[0] = 1, the empty payment. Every other cell starts at 0.

3. Order: the coin values one by one in the outer loop, in the order they are read; for each coin c, x from c up to S.

4. Transition: ways[x] += ways[x - c].

5. Answer: ways[S].

Problem statements often call payments combinations and sequences permutations.

The first line of the input holds n, the number of coin values, and the amount S. The second line holds the n coin values, all different. The program prints the fewest coins (or -1 if S can't be paid) and then the number of payments. The fewest-coins part is the introduction's code without restoring the coins: each amount gets 1 plus the smallest of the counts for the amount minus each coin. For the main example the input is:

3 6
1 3 4

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9;

int main() {
    int n, S;
    cin >> n >> S;
    vector<int> coins(n);
    for (int i = 0; i < n; i++) cin >> coins[i];

    // fewest coins, as in the introduction; remove this block if you only count
    vector<int> f(S + 1, INF);
    f[0] = 0;
    for (int x = 1; x <= S; x++)
        for (int c : coins)
            if (c <= x && f[x - c] + 1 < f[x]) f[x] = f[x - c] + 1;
    cout << (f[S] >= INF ? -1 : f[S]) << "\n";

    // state: ways[x] = the number of payments of x with the coins let in so far
    vector<long long> ways(S + 1, 0);

    // base case: the empty payment pays 0
    ways[0] = 1;

    // order: coin values one by one, amounts upward
    for (int c : coins) {
        for (int x = c; x <= S; x++) {
            // transition: no coin c (already in ways[x]) + ends with coin c
            ways[x] += ways[x - c];
        }
    }

    // answer
    cout << ways[S] << "\n";
}

One vector is enough because, when ways[x] is about to be updated for coin c, it still holds the count from the coins let in before c, the cell above in Fig. 4. The cell ways[x - c] was already updated for c, so it counts payments that may contain c, the cell to the left in the same row. Fig. 6 shows the moment amount 6 is filled for the coin 3.

Fig. 5. Filling ways[6] for coin 3: 1 + 2 = 3.

For the fewest coins, the order of the two loops doesn't matter: the best payment has the same number of coins in any order, so both loop orders give the same row 0, 1, 2, 1, 1, 2, 2.

Each table has S + 1 cells, each updated once per coin, so the time is O(n \cdot S) and the memory is $O(S)$ (see time complexity).

When the order matters

When different orders are different answers (throws of a die that add up to n), the amounts go in the outer loop and the coins in the inner one. This is the sum rule from the start of the article: for coins 1, 3, 4 it fills the row 1, 1, 1, 2, 4, 6, 9. Replace the counting loop of the main program with this one; for the main example it prints 9.

    // order: amounts upward, every coin for each amount
    for (int x = 1; x <= S; x++) {
        for (int c : coins) {
            // transition: the sequence ends with coin c
            if (c <= x) ways[x] += ways[x - c];
        }
    }

Correctness proof

For the count of payments, the loops keep an invariant: after the coin values c_1, \dots, c_k are let in, the cell for amount $x$ holds the number of payments of $x$ that use only these values.

Before any coin, only the empty payment exists, and it pays 0: the base case. Now let c_k in and take a payment of $x$ with values among c_1, \dots, c_k. Either it has no coin c_k, and then it was counted before and is still in the cell, or it has at least one. Take one c_k away, and what remains is a payment of x - c_k with values among c_1, \dots, c_k, counted in the cell for x - c_k, already updated for c_k. Each payment of the second kind comes from exactly one payment of x - c_k, and the two kinds don't overlap, so every payment is counted once.

The proof needs the coin values to be positive and different. If a value appears twice, it is let in twice: coins 1, 1 and amount 2 give 3, though the only payment is 1 + 1, so remove duplicates first.

Common mistakes

• Putting the amounts in the outer loop when the order doesn't matter. ways[x] remembers only the amount, not which coins the payment already holds, so it can't keep the agreed order and counts sequences: for coins 1, 2 and amount 4 it gives 5 instead of 3. Put the coins in the outer loop.

• Taking the biggest coin first for the fewest coins. Coins 1, 3, 4 pay 6 as 4 + 1 + 1, three coins, but 3 + 3 needs two, so fill the table instead.

• Starting with ways[0] = 0. Every count is built from ways[0], so every cell stays 0. Set ways[0] = 1 for the empty payment.

• Running the inner loop downward. Each coin value can then be used at most once: for coins 1, 3, 4 and amount 6 the program prints 0 instead of 4. When coins are unlimited, run x upward from c.

Similar algorithms

Greedy algorithms give the fewest coins only for some coin systems, such as 1, 2, 5, 10, and each system needs its own proof.

Knapsack has items with weights and values, usually each at most once, so the inner loop runs downward.

BFS on a state graph also finds the fewest coins: the fewest steps from amount S to 0, where each step takes one coin, but it can't count the payments.

Practice