Algorithm · Dynamic Programming

The Fewest Coins.

Don't memorize coin change — watch the table fill. To make an amount with the fewest coins, first solve every smaller amount, then each new amount is just “one coin plus the best way to make the rest”. Build that up from 0 and the answer falls out — and you will see exactly why grabbing the biggest coin first can leave you worse off.

min coins · dp[a] = 1 + min(dp[a−coin]) · greedy fails
dp[a]

Fewest coins that sum to amount a. dp[0] = 0.

THE CHOICE

Try each coin c ≤ a: 1 + dp[a − c]. Keep the smallest.

BUILD UP

Fill amounts 0 → target; each reuses earlier answers.

GREEDY TRAP

Biggest-coin-first is not always optimal — DP is.

coin-change.sim — coins [1,3,4], make 6 with fewest
Ready

The array dp[a] holds the fewest coins to make amount a. dp[0] = 0. Press Step to fill each amount by trying every coin and keeping the smallest.

dp[a] = 1 + min over coins of dp[a − coin]
Amount
dp value

Small answers build the big one

The brute force tries every combination of coins — exponential. Dynamic programming notices that the best way to make an amount reuses the best way to make a smaller amount. So it fills a one-row table: dp[a] is the fewest coins for a, and to fill it you simply try dropping in each coin and asking how the leftover was best made — a value you already computed. One pass over the amounts, one look at each coin.

01

Base case

dp[0] = 0 — zero coins make zero. Everything else starts as “unreachable”.

02

Try every coin

For amount a, each coin c ≤ a offers 1 + dp[a − c] — one of that coin plus the best for the remainder.

03

Keep the minimum

dp[a] = 1 + min over coins of dp[a − c]. Fill amounts 0 up to the target.

04

Read the answer

dp[target] is the fewest coins; track the chosen coin per cell to reconstruct which coins.

Time
O(amount · coins)
Space
O(amount)
Greedy
not optimal
Class
Unbounded knapsack

Watch amount 6 with coins {1, 3, 4}: greedy grabs the biggest coin, 4, then must add 1 + 1 — three coins. The DP finds 3 + 3 — two coins. A locally biggest choice stranded greedy with an awkward remainder, which is exactly the trap dynamic programming avoids by considering every option. Coin change is really an unbounded knapsack: each coin is an item you may reuse freely.

SOLVE IT YOURSELF

Solve it: fewest coins

This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement coin_change(coins, amount): return the fewest coins that add up to amount (each coin usable any number of times), or -1 if it cannot be made. Build up dp[a] = fewest coins for amount a — that is O(amount × coins).

HINTS — 4 IDEAS
  1. Greedy (always take the biggest coin) fails — 6 from {1,3,4} is 3+3, not 4+1+1.
  2. Let dp[a] be the fewest coins to make amount a. dp[0] = 0; start every other entry at infinity.
  3. For each amount a and each coin c ≤ a: dp[a] = min(dp[a], dp[a − c] + 1).
  4. If dp[amount] is still infinity at the end, the amount is impossible → return -1.
CPython · WebAssembly

Check yourself

1 · What does dp[a] store?

Each cell is the optimal coin count for that amount, built from smaller amounts.

2 · Coins {1, 3, 4}, amount 6. Why is greedy wrong?

Taking the biggest coin first strands a bad remainder; DP considers all options and finds 3 + 3.

3 · Coin change is a special case of which problem?

Each coin is an item you can take any number of times — the unbounded knapsack shape.

Questions

When does greedy actually work for coin change?

For canonical coin systems (like US or Euro coins) greedy is optimal. But it is not guaranteed for arbitrary denominations, so DP is the safe general solution. Proving a system is canonical is itself non-trivial.

How do you count the number of ways instead of the fewest?

Change the recurrence to a sum: dp[a] += dp[a − coin], iterating coins in the outer loop to avoid counting permutations. It is the same table with addition instead of a min.

What if the amount is unreachable?

Leave unreachable amounts as infinity; if dp[target] stays infinity, no combination of coins makes it. Interview versions often ask you to return −1 in that case.

Build small, answer big — and skip the greedy trap.

Every amount reuses a smaller one. dp[target] is the fewest coins, guaranteed optimal.

Finished this one? 0 / 47 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms