DSA Coin Change

The problem

You have coins of a few values. You have as many of each coin as you need. The question asks for the fewest coins that add up to a target amount.

The answer is a count, not the coins themselves. If no mix of coins reaches the amount, the answer is -1. An amount of 0 needs no coins, so its answer is 0.

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

Read one row at a time. Coins [1, 2, 5] make 11 as 5 + 5 + 1, which is three coins. Coins [1, 3, 4] make 6 as 3 + 3, which is two coins. A single 2 coin can never make 3, so that row answers -1.

Why greedy fails

The first idea most people try is greedy. Take the largest coin that fits. Repeat until nothing is left.

Greedy is fast, and it works for real money in many countries. It fails on made-up coin sets. The failure is quiet: greedy still returns an answer, just not the smallest one.

coins = [1, 3, 4]
amount = 6
remaining = amount
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 grabs the 4 first. That one grab blocks the better pair. The rest of the amount can then only be filled with 1s, and the count climbs to three.

The lesson is general. A choice that looks best now can block a better mix later. A correct method has to consider more than the first grab.

Brute force: try every last coin

Every solution for an amount has a last coin. Some coin was placed last, and before it sat a solution for the smaller amount that remains.

That gives a recipe. To solve amount a, try each coin as the last coin. For each try, solve a minus that coin, then add one. Keep the smallest total.

calls = 0

def fewest(amount):
    global calls
    calls += 1
    if amount == 0:
        return 0
    best = None
    for coin in [1, 3, 4]:
        if coin <= amount:
            rest = fewest(amount - coin)
            if rest is not None:
                best = rest + 1 if best is None else min(best, rest + 1)
    return best

print("fewest(6):", fewest(6))
print("calls:", calls)

The code finds the right answer: two coins. It also makes many calls to get it. The counter prints the bill.

The base case is amount 0, which needs no coins. An amount that no coin fits returns None. None means this branch cannot be completed, so the caller skips it.

The same subproblems repeat

Look at what the recursion computes. fewest(6) needs fewest(5), fewest(3) and fewest(2). Each of those needs smaller amounts again. The same amounts come back many times.

Repeated subproblems are the signal for dynamic programming. Solve each amount once. Store the answer. Reuse it every later time it is asked for.

calls = 0
memo = {0: 0}

def fewest(amount):
    global calls
    calls += 1
    if amount in memo:
        return memo[amount]
    best = None
    for coin in [1, 3, 4]:
        if coin <= amount:
            rest = fewest(amount - coin)
            if rest is not None:
                best = rest + 1 if best is None else min(best, rest + 1)
    memo[amount] = best
    return best

print("fewest(6):", fewest(6))
print("calls:", calls)
print("memo:", memo)

The memo holds one entry per amount. Each amount is computed once and read many times, so the call count drops even on this tiny amount. The shape of the fix is now visible: the stored answers are a table, and the table can be filled directly, without recursion.

The optimal solution: one table, bottom up

Fill a table in increasing order instead. dp[a] means the fewest coins that make amount a. That one sentence is the state, and the whole solution follows from it.

Start with dp[0] = 0. For each later amount, try every coin as the last coin. The candidate is dp[a - coin] + 1. Keep the smallest candidate.

One problem remains. Some amounts cannot be made at all. The table needs a marker for them, so the code uses a sentinel: amount + 1. No real answer can reach that value, because even an all-smallest-coin solution uses at most amount coins. A cell that still holds the sentinel at the end reports -1.

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

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

All four cases from the start of the article pass. The greedy counterexample now answers two. The impossible case answers -1.

Walkthrough: filling the table for 6

Watch the table fill for coins [1, 3, 4] and amounts 0 to 6. The sentinel here is 7. A 7 in a cell means no mix found yet.

coins = [1, 3, 4]
amount = 6
sentinel = amount + 1
dp = [sentinel] * (amount + 1)
dp[0] = 0
print("start:", dp)
for a in range(1, amount + 1):
    for coin in coins:
        if coin <= a:
            dp[a] = min(dp[a], dp[a - coin] + 1)
    print("after amount", a, ":", dp)

Amount 1 takes one 1 coin. Amount 2 takes two. Amount 3 drops to one the moment the 3 coin is tried as its last coin.

Amount 6 is the interesting cell. Its three tries read dp[5] + 1 = 3, dp[3] + 1 = 2 and dp[2] + 1 = 3. The smallest is 2, from the 3 coin last. That matches 3 + 3.

Complexity

The table has amount + 1 cells. Each cell tries every coin once. The work is amount times the number of coins: O(amount x coins) time.

The memory is the table alone: O(amount) space. The memoised recursion uses the same table, plus a call stack. The bottom-up version drops the stack.

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

for amount in [10, 20, 40]:
    print("amount", amount, "steps:", dp_steps([1, 3, 4], amount))

calls = 0

def fewest(amount):
    global calls
    calls += 1
    if amount == 0:
        return 0
    best = None
    for coin in [1, 3, 4]:
        if coin <= amount:
            rest = fewest(amount - coin)
            if rest is not None:
                best = rest + 1 if best is None else min(best, rest + 1)
    return best

fewest(20)
print("brute force calls for amount 20:", calls)

Counts beat clocks here. The table's step count doubles when the amount doubles, exactly as the formula says. The brute-force call count for one small amount already dwarfs the table's whole run.

Edge cases and pitfalls

Amount 0 answers 0. The table starts with dp[0] = 0, and the function returns it before any coin is tried.

A coin larger than the amount is simply skipped. The coin <= a check is what skips it. Drop that check and the index a - coin goes negative, which in Python quietly reads the wrong cell instead of crashing.

The sentinel must be larger than any real answer. amount + 1 qualifies. A smaller marker, like 999 on a huge amount, can collide with a real count and report a possible amount as impossible.

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

print("amount 0:", coin_change([1, 3, 4], 0))
print("no coin fits:", coin_change([5], 3))
print("odd target, even coins:", coin_change([2], 3))
print("coins unordered:", coin_change([4, 1, 3], 6))
print("one big coin:", coin_change([2, 5, 10], 10))

The order of the coins changes nothing. The table tries every coin at every amount, so a shuffled coin list gives the same answers.