Coin Change

Interview Prep

StandardDynamic Programmingdpunbounded-knapsack

The problem

Given a list of coin denominations (with unlimited supply of each) and a target amount, return the minimum number of coins needed to make the amount, or −1 if impossible.

Why greedy fails

Take the largest coin that fits, repeat. This works for US currency but not in general. Counter-example: coins [1, 3, 4], amount 6. Greedy takes 4 then 1 + 1 = 3 coins. Optimal is 3 + 3 = 2 coins. The "biggest first" rule is locally optimal but globally wrong whenever a smaller coin enables a much better pairing. 

def coin_change_greedy(coins, amount):
    """WRONG in general — only works for canonical coin systems (e.g., US)."""
    coins = sorted(coins, reverse=True)
    count = 0
    for c in coins:
        while amount >= c:
            amount -= c
            count  += 1
    return count if amount == 0 else -1

# coins=[1,3,4], amount=6 -> greedy: 4+1+1 = 3 coins
# optimal:                         3+3   = 2 coins

Greedy works iff the coin system is "canonical" — a property that can be tested in polynomial time but is not in general guaranteed. Don't bet on it.

Pattern: unbounded knapsack DP

Let dp[a] be the minimum coins to make amount a. The recurrence is: dp[a] = 1 + min(dp[a − c]) over all coins c ≤ a. Base case dp[0] = 0. This is the "unbounded" knapsack flavor — each coin can be used any number of times, so we iterate amounts outer, coins inner, and read from dp[a − c] (same row).

Solution

def coin_change(coins: list[int], amount: int) -> int:
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    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
    return dp[amount] if dp[amount] != INF else -1

Trace

coins = [1, 3, 4], amount = 6

dp[0] = 0
dp[1] = min(dp[0]+1) = 1                          [1]
dp[2] = min(dp[1]+1) = 2                          [1,1]
dp[3] = min(dp[2]+1, dp[0]+1) = 1                 [3]
dp[4] = min(dp[3]+1, dp[1]+1, dp[0]+1) = 1        [4]
dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = 2        [4,1] or [1,1,3]
dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = 2        [3,3]

return dp[6] = 2

Complexity

This is pseudo-polynomial: it's polynomial in the numerical value of amount, not in the number of bits to represent it. For huge amounts with few coins, BFS on the implicit graph (states are amounts, edges are coin subtractions) can be faster in practice because it stops at the first time the target is reached.

Variations worth knowing