DSA Coin Change, First Taste

The problem

The coin change problem asks for the fewest coins that add up to a target amount. Coins come in a few fixed values. As many of each coin may be used as needed.

The answer is a count, not the coins themselves. An amount of 0 needs no coins. This first taste uses coin sets that include a 1 coin, so every amount can be made.

cases = [
    ([1, 2, 5], 11, 3),
    ([1, 3, 4], 6, 2),
    ([1, 3, 4], 11, 3),
    ([1, 2, 5], 0, 0),
]
for coins, amount, expected in cases:
    print("coins", coins, "amount", amount, "fewest:", expected)

Coins [1, 2, 5] make 11 as 5 + 5 + 1. That is three coins. Coins [1, 3, 4] make 6 as 3 + 3, which is two coins.

Intuition: the largest coin first is tempting

A first idea is greedy. Take the largest coin that fits. Then repeat on what remains.

One small case shows the trap. Coins [1, 3, 4] and amount 6 are enough. Greedy grabs the 4 and is then stuck filling the rest with 1 coins.

coins = [1, 3, 4]
remaining = 6
greedy = []
for coin in sorted(coins, reverse=True):
    while remaining >= coin:
        greedy.append(coin)
        remaining -= coin
print("greedy coins:", greedy)
print("greedy count:", len(greedy))
print("better coins: [3, 3]")
print("better count:", 2)

Greedy returns three coins. The pair 3 + 3 returns two. A correct method has to look past the first grab.

Brute force: try every last coin

Every way to make an amount has a last coin. Before that coin sits a way to make the smaller amount that remains. Trying each coin as the last coin covers every possibility.

calls = 0

def fewest(amount):
    global calls
    calls += 1
    if amount == 0:
        return 0
    return 1 + min(fewest(amount - c) for c in [1, 3, 4] if c <= amount)

for amount in [6, 10]:
    calls = 0
    print("amount", amount, "fewest:", fewest(amount), "calls:", calls)

The answers are right. The calls repeat the same amounts many times. Amount 5 is solved inside amount 6, inside amount 10, and on many branches between.

The fix is storage. Solve each amount once. Keep its count in a table and read it back.

The optimal solution: a table of fewest coins

The state is dp[a], the fewest coins that make amount a. That one sentence defines the table, and the whole solution follows from it.

The table starts with dp[0] = 0. Each later amount tries every coin as its last coin. Its count is one plus the count for the amount that remains, and the smallest try wins.

def coin_change(coins, amount):
    dp = [0] * (amount + 1)
    for a in range(1, amount + 1):
        dp[a] = 1 + min(dp[a - c] for c in coins if c <= a)
    return dp[amount]

for coins, amount in [([1, 2, 5], 11), ([1, 3, 4], 6), ([1, 3, 4], 11), ([1, 2, 5], 0)]:
    print("coins", coins, "amount", amount, "fewest:", coin_change(coins, amount))

All four cases from section 1 pass. The table fills upward, so every smaller amount is ready when a larger one needs it.

Walkthrough: filling the table up to 6

Watch the table fill for coins [1, 3, 4]. The printed line shows the whole table after each amount. The index of a cell is its amount.

coins = [1, 3, 4]
dp = [0]
print("amount 0:", dp)
for a in range(1, 7):
    dp.append(1 + min(dp[a - c] for c in coins if c <= a))
    print("amount", a, ":", dp)

Amount 3 drops to one coin when the 3 coin is tried. Amount 4 also takes one coin. Amount 5 takes two, as 4 + 1.

Amount 6 reads three cells. Its tries give dp[5] + 1 = 3, dp[3] + 1 = 2 and dp[2] + 1 = 3. The smallest is 2, and the last cell is the answer.

Complexity

The table has one cell per amount, and each cell tries every coin once, so the time is O(amount x coins).

The table is the only storage, so the space is O(amount).

calls = 0

def fewest(amount):
    global calls
    calls += 1
    if amount == 0:
        return 0
    return 1 + min(fewest(amount - c) for c in [1, 3, 4] if c <= amount)

def table_steps(coins, amount):
    steps = 0
    dp = [0] * (amount + 1)
    for a in range(1, amount + 1):
        best = None
        for c in coins:
            steps += 1
            if c <= a:
                cand = dp[a - c] + 1
                best = cand if best is None else min(best, cand)
        dp[a] = best
    return steps

for amount in [10, 20, 40]:
    print("amount", amount, "table steps:", table_steps([1, 3, 4], amount))
calls = 0
fewest(20)
print("brute force calls for amount 20:", calls)

The step count doubles when the amount doubles. That matches the formula. The brute force calls for amount 20 alone dwarf a whole table run.

Edge cases and pitfalls

Amount 0 answers 0 before any coin is tried. The table starts there. Every other cell builds on it.

A coin larger than the amount is skipped. The check that the coin fits is what skips it. Without the check, the code reads a cell with a negative index and silently uses the wrong amount.

def coin_change(coins, amount):
    dp = [0] * (amount + 1)
    for a in range(1, amount + 1):
        dp[a] = 1 + min(dp[a - c] for c in coins if c <= a)
    return dp[amount]

print("amount 0:", coin_change([1, 3, 4], 0))
print("amount 1:", coin_change([1, 3, 4], 1))
print("big coin skipped:", coin_change([1, 50], 3))
print("coins unordered:", coin_change([4, 1, 3], 6))

The order of the coins changes nothing. Every coin is tried at every amount. A shuffled coin list gives the same counts.

Amounts that no mix of coins can make are deferred to the Intermediate coin-change article, which gives the full treatment including that impossible case.