Coin Change

Build a table where each entry is the fewest coins needed for that amount. For every amount from one upwards, try each coin as the last coin used and take the smallest result.

def coin_change(coins, amount):
    table = [0] + [float('inf')] * amount
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value and table[value - coin] + 1 < table[value]:
                table[value] = table[value - coin] + 1
    return -1 if table[amount] == float('inf') else table[amount]


print(coin_change([1, 2, 5], 11))
print(coin_change([2], 3))

The outputs are 3 and minus one. Eleven can be made with three coins, for example five plus five plus one, and the amount three cannot be made at all from twos, so no solution exists.

The mechanism is the recurrence. Any solution for an amount ends with some coin, and removing that coin leaves a solution for a smaller amount, so the minimum is one plus the minimum over the smaller amounts. Filling the table in increasing order of amount guarantees that every smaller amount is already solved.

The trade-off to name is that the table is linear in the amount, which is fine for a few thousand but becomes the bottleneck for very large amounts. The bottom up version also allows unlimited copies of each coin, whereas the version where each coin may be used once needs the coins in the outer loop, and swapping the two loops is exactly the difference between combinations and permutations. It is worth saying which convention you are using, because the loop order silently decides it.

Keep a table of counts, seed it with one way to make zero, and process the coins in the outer loop so that each combination is counted once rather than once per ordering.

def coin_combinations(coins, amount):
    table = [0] * (amount + 1)
    table[0] = 1
    for coin in coins:
        for value in range(coin, amount + 1):
            table[value] += table[value - coin]
    return table[amount]


print(coin_combinations([1, 2, 5], 5))
print(coin_combinations([2], 3))

The outputs are 4 and 0. Five can be made in four ways with coins of one, two and five: the single five, two plus two plus one, two plus one plus one plus one, and five ones. The amount three cannot be made from twos alone.

The mechanism is the loop order. Putting the coins outside and the amounts inside means each coin is considered once, so a combination is built up in a fixed order of coins and counted a single time. Reversing the loops would count the orderings as well, so two plus one and one plus two would be counted separately.

The trade-off to name is the same one as the minimum coin count, and the loop order is the single most important detail in both. The base case of one way to make zero is what makes the count work, since there is exactly one empty combination. The counts can also grow very large, so a fixed width integer would overflow for a big amount, and the space is linear in the amount.

When the amount is enormous but the number of distinct coins is small, you have to change what you iterate over. Instead of a table indexed by amount, you iterate over the coins and search over the possible counts of each coin.

That means the state is a tuple of counts, one per coin, rather than a single number. With two coins the problem becomes a two pointer scan: for each possible count of the first coin, the remaining amount determines the count of the second, and you check whether the remainder is divisible. With more coins the search space grows exponentially in the number of coin types, so it becomes a backtracking search with pruning.

The mechanism is that the number of distinct coin values is often far smaller than the target amount, and the useful state space is the combinations of counts rather than every intermediate amount.

The trade-off to name is that you lose the linear time guarantee. The table version is O of amount times the number of coins, which is unbeatable when the amount fits, but it cannot handle an amount of ten to the eighteen. The count based search is O of the number of count combinations, which is fine when the coin set is small and the amount is huge. There is also a middle ground worth mentioning, since for the minimum coin problem a greedy approach works when the coin system is canonical, and a number theoretic solution exists for the two coin case, but neither generalises.