Python programs / Dynamic programming / Coin change

Python Program for the Coin Change Problem (Minimum Coins)

Intermediate Dynamic programming Time O(n × k) Space O(n)

Finds the fewest coins that add up to an amount by solving every smaller amount first, or -1 when no mix of the coins makes it.

The coin change problem asks for the fewest coins that add up to an amount, using as many of each coin as you like. Paying the biggest coin that fits, again and again, works for most real coin sets but not for every set: with coins of 1, 3 and 4 it pays 6 as 4 + 1 + 1, three coins, when 3 + 3 needs only two. With coins of 2 and 5 it can't pay 6 at all: after a 5, the 1 left over can't be made, though 2 + 2 + 2 works. Dynamic programming finds the true fewest by working out every amount from 1 up, each one from the smaller amounts before it.

Program

def min_coins(coins, amount):
    """The fewest coins that add up to amount, or -1 if none do."""
    # fewest[a]: the fewest coins for amount a (inf: no way yet)
    fewest = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                fewest[a] = min(fewest[a], fewest[a - coin] + 1)
    if fewest[amount] == float("inf"):
        return -1  # no mix of the coins makes this amount
    return fewest[amount]


coins = [2, 5]
print("Fewest coins for 6:", min_coins(coins, 6))
print("Fewest coins for 3:", min_coins(coins, 3))

Open in the editor Download coin_change.py

Output

Fewest coins for 6: 3
Fewest coins for 3: -1

How it works

  1. fewest has one entry for each amount from 0 to amount. Amount 0 needs no coins; every other amount starts at infinity, float("inf"), meaning no way to pay it has been found yet. Infinity is larger than any number, so min() replaces it as soon as a real count turns up.
  2. The amounts are worked out in order, from 1 up, trying each coin as the last one paid.
  3. If the coin fits, paying it leaves a - coin, a smaller amount whose fewest coins are already known. That count plus this one coin is a way to pay a, and fewest[a] keeps the smallest count found. When a - coin can't be paid, inf + 1 is still infinity, so it changes nothing.
  4. If the amount is still at infinity at the end, no mix of the coins makes it, and the function returns -1. Otherwise it returns the count.
  5. With coins of 2 and 5, the program asks for 6, which takes three 2s, and for 3, which can't be made.

The list for 6, one amount at a time:

Amount A 2 last A 5 last Fewest
0 0
1 doesn't fit doesn't fit inf
2 fewest[0] + 1 = 1 doesn't fit 1
3 fewest[1] + 1 = inf doesn't fit inf
4 fewest[2] + 1 = 2 doesn't fit 2
5 fewest[3] + 1 = inf fewest[0] + 1 = 1 1
6 fewest[4] + 1 = 3 fewest[1] + 1 = inf 3

So 6 takes 3 coins: 2 + 2 + 2. The call for 3 builds the same list up to 3, where the entry is still infinity, so it returns -1.

Time and space complexity

TimeO(n × k)
Extra spaceO(n)

For an amount n and k coin values, the inner loop runs n × k times in all, each a fixed amount of work, so the time is O(n × k). The list holds n + 1 counts: O(n) extra space.

Other ways to write it

With recursion and lru_cache

Top-down: the fewest coins for an amount is one more than the fewest for what's left after the best last coin. lru_cache, a decorator, remembers each amount's answer, so each is worked out once.

from functools import lru_cache

def min_coins(coins, amount):
    @lru_cache(maxsize=None)
    def fewest(a):
        if a == 0:
            return 0
        best = float("inf")
        for coin in coins:
            if coin <= a:
                best = min(best, fewest(a - coin) + 1)
        return best

    answer = fewest(amount)
    return -1 if answer == float("inf") else answer

print(min_coins([1, 3, 4], 6), min_coins([2, 5], 3))

Which coins, not only how many

A second list, last, records the coin that gave each amount its fewest count. Paying back from the amount, one last coin at a time, lists the coins.

def coins_used(coins, amount):
    fewest = [0] + [float("inf")] * amount
    last = [0] * (amount + 1)
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and fewest[a - coin] + 1 < fewest[a]:
                fewest[a] = fewest[a - coin] + 1
                last[a] = coin
    if fewest[amount] == float("inf"):
        return None
    used = []
    while amount > 0:
        used.append(last[amount])
        amount -= last[amount]
    return used

print(coins_used([1, 3, 4], 6), coins_used([2, 5], 11))

Try it yourself

  • Use coins of 1, 3 and 4 for an amount of 6. The answer is 2 (3 + 3), where paying the biggest coin first would take 3.
  • Pay 7 and 11 with coins of 2 and 5. They take 2 coins (5 + 2) and 4 coins (5 + 2 + 2 + 2).
  • Try a real set of coins, such as British pence, [1, 2, 5, 10, 20, 50], for 88p. It takes 6 coins.
  • Count the ways to make the amount instead of the fewest coins: start with ways = [1] + [0] * amount, loop over the coins on the outside and the amounts on the inside, and add ways[a - coin] to ways[a]. Coins of 1, 2 and 5 make 5 in 4 ways.

More dynamic programming programs

Share this program