Python Arena
Start learning
Step 3 of 6

Coin change

A vending machine has to give change. With the coins 1, 5, 10 and 25, the obvious way is greedy, like fitting the most meetings into a room in the module on sorting: take the biggest coin that fits, again and again. For these coins greedy happens to give the fewest coins. For others it doesn't:

def greedy(coins, amount):
    count = 0
    for coin in sorted(coins, reverse=True):
        count += amount // coin       # as many of this coin as fit
        amount %= coin
    return count


print(greedy([1, 5, 10, 25], 63))
print(greedy([1, 4, 5], 8))
Output
6
4

63 is 25 + 25 + 10 + 1 + 1 + 1, six coins. But 8 comes out as 5 + 1 + 1 + 1, four coins, when 4 + 4 needs only two. Once greedy has taken the 5, it's stuck with the 3 that's left, and it never goes back to ask whether a smaller first coin would leave a better rest. DP does ask that, for every coin, and it can afford to: it works out each amount only once.

The fewest coins

Write best[a] for the smallest number of coins that add up to a. However the best way to make a looks, it ends with some last coin c. Take that coin away and a - c is left, made in as few coins as possible too, or there would be a better way to make a. So try each coin c that fits, and best[a] is the smallest best[a - c] + 1 among them. No coins at all make 0, so best[0] = 0, and the list fills in for a = 1, 2, 3 and on: a - c is always a smaller amount, already done.

Some amounts can't be made at all: with only 3s and 5s, there's no way to make 7. They need a value that means "impossible" and never wins the smallest. math.inf is a float bigger than every number, and inf + 1 is still inf, so an amount that can't be made stays that way:

from math import inf


def fewest_table(coins, amount):
    best = [0] + [inf] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and best[a - coin] + 1 < best[a]:
                best[a] = best[a - coin] + 1
    return best


print(fewest_table([1, 4, 5], 8))
print(fewest_table([5, 3], 7))
Output
[0, 1, 2, 3, 1, 1, 2, 3, 2]
[0, inf, inf, 1, inf, 1, 2, inf]

best[8] is 2, from best[4] + 1: a 4 on top of the best way to make 4. The 5 was tried too, but best[3] + 1 is 4. In the second table, 1, 2, 4 and 7 can't be made, and their entries are still inf. A function that answers -1 for "impossible" checks for inf at the end. With k coin values, each amount looks at k coins: O(amount × k) time and O(amount) memory. That depends on the amount itself, not on its number of digits: an amount of a billion needs a billion entries.

Counting the ways

In how many ways can you make 4 with the coins 1, 2 and 3? There's 3 + 1, 2 + 2, 2 + 1 + 1 and 1 + 1 + 1 + 1: four, where 3 + 1 and 1 + 3 count as the same way. Let ways[a] be the number of ways to make a, with ways[0] = 1 (the empty way). Here the order of the two loops decides what you count:

def combinations(coins, amount):
    ways = [1] + [0] * amount
    for coin in coins:                       # coins outside
        for a in range(coin, amount + 1):
            ways[a] += ways[a - coin]
    return ways[amount]


def orderings(coins, amount):
    ways = [1] + [0] * amount
    for a in range(1, amount + 1):           # amounts outside
        for coin in coins:
            if coin <= a:
                ways[a] += ways[a - coin]
    return ways[amount]


print(combinations([1, 2, 3], 4), orderings([1, 2, 3], 4))
Output
4 7
  • Coins outside: the first round makes every amount with 1s only, the second adds 2s on top of those ways, the third adds 3s. Every way is built with its coins in the order of the list, so 1 + 1 + 2 is built once, and never as 2 + 1 + 1. That counts combinations.
  • Amounts outside: for each amount the last coin can be any coin, so 2 + 1 + 1, 1 + 2 + 1 and 1 + 1 + 2 are three different ways. That counts orderings, like the climbs of the last step, where 1 + 2 and 2 + 1 were different.

Mixing the two up is the classic coin change bug: no error, just a bigger number. Both cost O(amount × k) time and O(amount) memory. A backtracking search that took or left each coin, coming back to the same coin again and again, would count the ways one at a time, and that takes as long as there are ways: 642 million for an amount of 300 with the coins 3 to 12.

Your task

Challenge 1 of 3

This program fills the table of the ways to make each amount from 0 to 7 with the coins 2 and 3, coins outside, and prints the table after each coin's round. What does it print? Type each line it prints.

Challenge 2

Write min_coins(coins, amount). It returns the smallest number of coins whose values add up to amount, with as many coins of each value as you like. When no mix of the coins reaches amount exactly, it returns -1. The tests go up to amounts of 80,000, so fill a table from the bottom up.

For example, print(min_coins([1, 4, 5], 8), min_coins([5, 3], 7)) prints:

2 -1

Challenge 3

Write count_ways(coins, amount): the number of different ways to make amount from the coins, using each coin value any number of times, where ways with the same coins in another order count once. The coin values are different positive numbers.

A search that tries the coins one by one, the backtracking way, finds the ways one at a time. That's far too slow here: the tests include an amount of 300 with the coins 3 to 12, which can be made in 642 million ways, and others go up to an amount of 20,000, far deeper than recursion can go. Fill a table, with the loops in the order that counts combinations.

For example, count_ways([2, 5, 3, 6], 10) returns 5 (5 + 5, 2 + 2 + 6, 2 + 3 + 5, 2 + 2 + 3 + 3 and 2 + 2 + 2 + 2 + 2):

5
Previous: Bottom-up tables Next: Paths through a grid