Skip to content

Coin change

Find the fewest coins that make an amount, when each kind of coin can be used as often as you like. And, with almost the same table, count how many different ways the amount can be made.

Time Extra space Coins Output
\(O(k \cdot A)\) for \(k\) coin kinds and amount \(A\) \(O(A)\) any positive values fewest coins (and which), or the number of ways

The idea

With US coins (1, 5, 10 and 25 cents), the obvious method works: take the largest coin that fits, repeat. But that greedy rule fails for other coin sets. With coins 1, 3 and 4, the amount 6 is best made as 3 + 3 (two coins), while greedy takes 4 + 1 + 1 (three).

Dynamic programming does not guess. Ask: what was the last coin? If the last coin was \(c\), the rest is the best way to make \(x - c\). So

\[\text{best}[x] = 1 + \min_{c \le x} \text{best}[x - c], \qquad \text{best}[0] = 0.\]

Fill best[1], best[2], ..., best[A] in order; each needs only smaller amounts, already done.

Counting the ways is similar, with a twist: to count \(\{1, 2\}\) and \(\{2, 1\}\) as the same set, loop over the coins on the outside. Then each set is built in one fixed order of coin kinds.

How it works

Fewest coins

  1. best[0] = 0; every other entry starts at infinity ("not possible yet").
  2. For x from 1 to A, for each coin c ≤ x: if best[x - c] + 1 is smaller, store it, and remember c in last[x].
  3. If best[A] is still infinity, the amount cannot be made. Otherwise follow last[] back from A to list the coins.

Number of ways

  1. ways[0] = 1 (the empty set of coins).
  2. For each coin c, for x from c up to A: ways[x] += ways[x - c].

Code

def min_coins(coins, amount):
    """The fewest coins that add up to amount (any coin may be used many times), and which coins; -1 if impossible."""
    INF = float("inf")
    best = [0] + [INF] * amount              # best[x] = fewest coins for the amount x
    last = [0] * (amount + 1)                # last[x] = the coin used last in that best way
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and best[x - c] + 1 < best[x]:
                best[x] = best[x - c] + 1
                last[x] = c
    if best[amount] == INF:
        return -1, []
    used, x = [], amount
    while x > 0:                             # walk back through the choices
        used.append(last[x])
        x -= last[x]
    return best[amount], used


def count_ways(coins, amount):
    """How many different sets of coins add up to amount (order does not matter)."""
    ways = [1] + [0] * amount                # one way to make 0: no coins
    for c in coins:                          # coins in the outer loop, so each set is counted once
        for x in range(c, amount + 1):
            ways[x] += ways[x - c]
    return ways[amount]


if __name__ == "__main__":
    print(*min_coins([1, 3, 4], 6))
    print(*min_coins([1, 5, 10, 25], 63))
    print(*min_coins([2], 3))
    print(count_ways([1, 2, 5], 5), count_ways([1, 5, 10, 25], 100))

import java.util.ArrayList;
import java.util.List;

public class CoinChange {
    static List<Integer> used = new ArrayList<>();

    /** The fewest coins that add up to amount (any coin may be used many times), and which coins; -1 if impossible. */
    static int minCoins(int[] coins, int amount) {
        final int INF = Integer.MAX_VALUE;
        int[] best = new int[amount + 1];             // best[x] = fewest coins for the amount x
        int[] last = new int[amount + 1];             // last[x] = the coin used last in that best way
        for (int x = 1; x <= amount; x++) {
            best[x] = INF;
            for (int c : coins)
                if (c <= x && best[x - c] != INF && best[x - c] + 1 < best[x]) {
                    best[x] = best[x - c] + 1;
                    last[x] = c;
                }
        }
        used = new ArrayList<>();
        if (best[amount] == INF) return -1;
        for (int x = amount; x > 0; x -= last[x]) used.add(last[x]);   // walk back through the choices
        return best[amount];
    }

    /** How many different sets of coins add up to amount (order does not matter). */
    static long countWays(int[] coins, int amount) {
        long[] ways = new long[amount + 1];
        ways[0] = 1;                                  // one way to make 0: no coins
        for (int c : coins)                           // coins in the outer loop, so each set is counted once
            for (int x = c; x <= amount; x++) ways[x] += ways[x - c];
        return ways[amount];
    }

    public static void main(String[] args) {
        int k = minCoins(new int[]{1, 3, 4}, 6);
        System.out.println(k + " " + used);
        k = minCoins(new int[]{1, 5, 10, 25}, 63);
        System.out.println(k + " " + used);
        k = minCoins(new int[]{2}, 3);
        System.out.println(k + " " + used);
        System.out.println(countWays(new int[]{1, 2, 5}, 5) + " " + countWays(new int[]{1, 5, 10, 25}, 100));
    }
}

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

// The fewest coins that add up to amount (any coin may be used many times), and which coins; -1 if impossible.
int minCoins(const vector<int>& coins, int amount, vector<int>& used) {
    vector<int> best(amount + 1, INT_MAX);           // best[x] = fewest coins for the amount x
    vector<int> last(amount + 1, 0);                 // last[x] = the coin used last in that best way
    best[0] = 0;
    for (int x = 1; x <= amount; x++)
        for (int c : coins)
            if (c <= x && best[x - c] != INT_MAX && best[x - c] + 1 < best[x]) {
                best[x] = best[x - c] + 1;
                last[x] = c;
            }
    used.clear();
    if (best[amount] == INT_MAX) return -1;
    for (int x = amount; x > 0; x -= last[x]) used.push_back(last[x]);   // walk back through the choices
    return best[amount];
}

// How many different sets of coins add up to amount (order does not matter).
long long countWays(const vector<int>& coins, int amount) {
    vector<long long> ways(amount + 1, 0);
    ways[0] = 1;                                     // one way to make 0: no coins
    for (int c : coins)                              // coins in the outer loop, so each set is counted once
        for (int x = c; x <= amount; x++) ways[x] += ways[x - c];
    return ways[amount];
}

void show(int k, const vector<int>& v) {
    cout << k << " [";
    for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
    cout << "]\n";
}

int main() {
    vector<int> used;
    int k = minCoins({1, 3, 4}, 6, used); show(k, used);
    k = minCoins({1, 5, 10, 25}, 63, used); show(k, used);
    k = minCoins({2}, 3, used); show(k, used);
    cout << countWays({1, 2, 5}, 5) << " " << countWays({1, 5, 10, 25}, 100) << "\n";
}

Output:

  • 2 [3, 3]: coins 1, 3 and 4 make 6 with two coins.
  • 6 [1, 1, 1, 10, 25, 25]: 63 cents in US coins.
  • -1 []: 3 cannot be made from 2s.
  • 4 242: there are 4 ways to make 5 from 1, 2 and 5, and 242 ways to make a dollar from pennies, nickels, dimes and quarters.

When to use it

  • Any "fewest pieces" problem with unlimited copies: stamps, standard lengths of pipe, packaging sizes.
  • Checking whether a coin system is safe for greedy: compare greedy with DP for all amounts up to the sum of the two largest coins (see "The math" below).
  • Counting combinations: the number of ways to score a total in a game with fixed point values.

Common mistakes

  • Using greedy for coin sets where it is not safe.
  • Swapping the loops when counting: with amounts on the outside, \(1 + 2\) and \(2 + 1\) are counted as two ways (that counts orderings, which is a different, also useful, question).
  • Adding 1 to infinity: in Java and C++, Integer.MAX_VALUE + 1 wraps around to a negative number; the code checks for "not possible" before adding.
  • Overflow when counting: the number of ways grows very fast; use 64-bit integers or a modulus.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: coins 1, 3, 4 and the amount 6
\(x\) try coin 1 try coin 3 try coin 4 best[\(x\)] last coin
0 0
1 best[0] + 1 = 1 1 1
2 best[1] + 1 = 2 2 1
3 best[2] + 1 = 3 best[0] + 1 = 1 1 3
4 best[3] + 1 = 2 best[1] + 1 = 2 best[0] + 1 = 1 1 4
5 best[4] + 1 = 2 best[2] + 1 = 3 best[1] + 1 = 2 2 1
6 best[5] + 1 = 3 best[3] + 1 = 2 best[2] + 1 = 3 2 3

Walk back from 6: last coin 3, leaving 3; last coin 3, leaving 0. Answer: 3 + 3.

Counting the ways to make 5 from 1, 2, 5: after coin 1, ways = [1, 1, 1, 1, 1, 1]; after coin 2, [1, 1, 2, 2, 3, 3]; after coin 5, [1, 1, 2, 2, 3, 4]. The four ways: 5; 2+2+1; 2+1+1+1; 1+1+1+1+1.

The math: why the recurrence is right, and when greedy is safe

Correctness. Take any best way to make \(x > 0\) and remove one coin \(c\) from it. What is left makes \(x - c\), and it must be a best way for \(x - c\) (otherwise swapping in a better one would improve \(x\)). So \(\text{best}[x] = 1 + \text{best}[x - c]\) for that \(c\), and taking the minimum over all \(c\) finds it.

Counting. Let \(W_j(x)\) be the number of ways to make \(x\) with the first \(j\) coin kinds. Either coin \(j\) is not used, or it is used at least once:

\[W_j(x) = W_{j-1}(x) + W_j(x - c_j).\]

The inner loop going upwards over \(x\) computes exactly this in one array.

Time. \(A\) amounts × \(k\) coins = \(O(kA)\). That is pseudo-polynomial: polynomial in the value \(A\), but exponential in the number of digits used to write \(A\). The general problem (with the amount written in binary) is NP-hard, so no known algorithm is polynomial in the number of digits.

When greedy is safe. A coin system is called canonical when greedy is always optimal. Kozen and Zaks showed that if greedy fails at all, it already fails at some amount below \(c_{k-1} + c_k\) (the two largest coins), so a DP over that range is a complete test. Pearson gave an \(O(k^3)\) test.

Watch it step by step

The red cell is being filled, the orange cell is best[x - c]. At the end the purple cells are the walk back.

Variations and related ideas
  • Each coin at most once: that is the 0/1 knapsack shape; loop amounts downwards.
  • Ordered ways (compositions): swap the loops; amounts outside, coins inside.
  • Unbounded knapsack: coins with values and weights, maximize value; the same loop as fewest coins.
  • Frobenius number: for two coins \(a\) and \(b\) with no common factor, the largest amount that cannot be made is \(ab - a - b\).

See also

References

  • D. Kozen and S. Zaks, "Optimal bounds for the change-making problem", Theoretical Computer Science 123(2), 1994.
  • D. Pearson, "A polynomial-time algorithm for the change-making problem", Operations Research Letters 33(3), 2005.
  • T. H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 14 (dynamic programming).