Coin Change

Coin Change is the classic "fewest pieces" dynamic-programming problem. It teaches a move you will reuse everywhere: build the answer for a big target out of the answers for smaller targets you have already solved.

The idea

Greedily grabbing the biggest coin can fail, so we solve it carefully with dynamic programming. Define dp[a] = the fewest coins needed to make amount a. The base case is easy: dp[0] = 0, because zero coins make the amount 0.

Now the key question for any amount a: what was the last coin I added? If the last coin was coin, then before adding it I had already made a − coin — and the best way to do that is dp[a - coin]. So that choice costs 1 + dp[a - coin]. We do not know which coin is last, so we try every coin and keep the smallest:

dp[a] = min over coins of (1 + dp[a - coin])

We fill dp from dp[1] up to dp[amount], left to right. Because every cell we read (dp[a - coin]) sits to the left of the cell we write (dp[a]), it is already final by the time we need it. The last cell, dp[amount], is the answer.

Walk through it

Step through the animation. The pointer a moves right one cell at a time. At each amount we try every coin that fits, read the cell dp[a − coin] (it lights up), add one coin, and write the smallest result into dp[a]. The dp line underneath shows the array filling up: 0, 1, 1, 2, 2, 1, 2. The final cell dp[6] = 2 is our answer.

Pseudocode

make an array dp of size amount + 1, filled with "infinity"
dp[0] = 0                         # zero coins make amount 0
for a from 1 to amount:
    for each coin in coins:
        if coin <= a:
            dp[a] = min(dp[a], 1 + dp[a - coin])
if dp[amount] is still "infinity": return -1
return dp[amount]

We use a big sentinel value (anything > amount, since no real answer needs more than amount coins) to mean "not reachable yet."

The Python solution

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

• dp has one slot per amount, from 0 up to amount. We start every slot at amount + 1, a stand-in for "infinity" — no real answer can use more than amount coins.
• dp[0] = 0 is the base case: it takes zero coins to make 0.
• The outer loop fills amounts left to right; the inner loop tries every coin.
• if coin <= a skips coins that are too big to fit into amount a.
• Line 7 is the recurrence: 1 + dp[a - coin] means "use one coin, plus the best way to make the rest." We keep the min across all coins.
• At the end, if dp[amount] never improved below the sentinel, no combination works, so we return -1.

Complexity

We trade O(amount) extra space (the dp array) to collapse exponential work into a simple double loop. Each of the amount cells does coins units of work, so the total is O(amount × coins).

When this pattern shows up

Practice