Coin Change

#How does it work?

The coin change problem asks for the fewest coins that pay an amount with the given denominations. Each coin can be used any number of times.

Greedy (always take the largest coin that fits) is right for real currencies like the euro, but not for every coin system. With coins 1, 3 and 4, greedy pays 6 as 4 + 1 + 1 = 3 coins, while 3 + 3 = 2 coins is enough.

DP solves every amount in turn: dp[a] = 1 + min(dp[a − c]), i.e. if the last coin is c, add one coin to the best solution for the remaining a − c. Keeping the chosen coin in last[a] lets you walk back to the coins themselves.

#Try it yourself

#Step by step

1. 01dp[0] = 0.
2. 02For each a = 1 … A and each coin c ≤ a, compute dp[a − c] + 1.
3. 03Write the smallest to dp[a] and the coin that gave it to last[a].
4. 04Start at A and subtract last[a] repeatedly to list the coins used.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

COINS = [1, 3, 4]
INF = float("inf")


def min_coins(amount: int):
    """Returns (fewest coins, the coins used)."""
    dp = [0] + [INF] * amount
    last = [0] * (amount + 1)  # the coin that gave dp[a]
    for a in range(1, amount + 1):
        for c in COINS:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                last[a] = c
    used, a = [], amount
    while a > 0:
        used.append(last[a])
        a -= last[a]
    return dp[amount], used


def greedy(amount: int) -> int:
    """Largest coin first: fast, but not always the fewest."""
    count = 0
    for c in sorted(COINS, reverse=True):
        count += amount // c
        amount %= c
    return count


count, used = min_coins(6)
print(count)
print(" ".join(map(str, used)))  # 3 + 3
print(greedy(6))                 # 4 + 1 + 1: one coin more

#Complexity

A is the amount and k the number of denominations. Like knapsack it is pseudo-polynomial: the table grows with the amount. With the loops reordered, the same table also answers "in how many different ways can we pay?".

#When to use it?

Making change at tills and ATMs, reaching a score in a game with the fewest moves, and completing a target as efficiently as possible from units of resources. It is also a good example of when greedy is and isn't enough.

#Practice

Log in to answer questions and save your progress.