Coin Change

Coin change asks for the fewest coins that add up to a target amount. The obvious move — grab the biggest coin that fits, repeat — is the greedy heuristic, and on the wrong denominations it overshoots. Dynamic programming solves every smaller amount first and reuses those answers, running in O(amount × coins) time and always returning the true minimum.

The engineering takeaway is to trust greedy only on coin systems designed for it. For arbitrary or custom denominations, reach for DP — or first prove the greedy-choice property actually holds. This lesson runs both strategies on one number line, where each jump or arc spans exactly one coin's value, so you can watch greedy strand itself while DP fills the line left to right and keeps the cheapest result at every amount.

How Coin Change Works

Greedy is a single pass. Start with remaining = amount. Repeatedly take the largest coin that is not bigger than remaining, subtract it, and count it. If you land exactly on zero you have an answer; if you get stranded on a remainder no coin can cover, greedy has failed. It is fast and it is intuitive, and that intuition is the trap.

DP never commits to a coin early. The state is dp[a]: the minimum number of coins that make amount a. The base case is dp[0] = 0 — zero coins make zero. Every other amount starts at infinity, meaning "not yet reachable."

To fill dp[a], the algorithm looks at each coin c. If c fits (c ≤ a) and the smaller amount dp[a - c] is already solved, then one candidate answer is dp[a - c] + 1: make a - c cheaply, then add one coin. dp[a] becomes the minimum over all coins of those candidates. If no coin produces a finite candidate, dp[a] stays infinity.

The reason this beats greedy is that dp[a] is chosen only after every cheaper amount is final. Greedy decides the first coin and lives with the consequences; DP lets every sub-amount vote. When the table is full, dp[amount] is the answer, or -1 if it is still infinity. To recover the actual coins, store which coin won each cell and trace backward from amount, subtracting the winning coin until you reach zero.

Coin Change Step by Step

The default run uses coins 1, 3, 4 and amount 6. This is the smallest classic case where greedy is beaten.

Greedy first. Remaining is 6. The largest coin that fits is 4, so greedy takes it; remaining is 2. Now 4 and 3 are both too big, so greedy takes 1, leaving 1, then takes 1 again, leaving 0. Greedy used three coins: 4 + 1 + 1. It made exact change, but that early 4 forced two awkward 1s.

Now DP. Set dp[0] = 0; every other cell starts at infinity.

• dp[1]: 4 and 3 are too big; coin 1 reads dp[0] + 1 = 1. So dp[1] = 1.
• dp[2]: only coin 1 fits, reading dp[1] + 1 = 2. So dp[2] = 2.
• dp[3]: coin 3 reads dp[0] + 1 = 1; coin 1 reads dp[2] + 1 = 3. The minimum is 1, using coin 3. So dp[3] = 1.
• dp[4]: coin 4 reads dp[0] + 1 = 1; coin 3 gives 2; coin 1 gives 2. The minimum is 1, using coin 4. So dp[4] = 1.
• dp[5]: coin 4 reads dp[1] + 1 = 2; coin 3 gives 3; coin 1 reads dp[4] + 1 = 2. The minimum is 2; coin 4 is recorded as the winner. So dp[5] = 2.
• dp[6]: coin 4 reads dp[2] + 1 = 3; coin 3 reads dp[3] + 1 = 2; coin 1 reads dp[5] + 1 = 3. The minimum is 2, using coin 3. So dp[6] = 2.

The full table is dp = [0, 1, 2, 1, 1, 2, 2].

Traceback. Start at amount 6, whose winning coin was 3; record a 3 and move to amount 3. Its winning coin was also 3; record another 3 and move to amount 0. The chosen coins are 3 + 3.

DP made 6 with two coins where greedy needed three. Two equal 3s beat one greedy 4 plus the leftovers it caused. That single-coin gap is the whole lesson.

Every cell DP reads from is already final — dp[3] was locked before dp[6] looked at it. That is why DP never has to backtrack: it only ever builds on answers it has already proven optimal. Switch to the Canonical preset (coins 1, 2, 5) to watch greedy and DP agree, and Impossible (coins 3, 5, amount 7) to watch the table return -1.

Time and Space Complexity

Greedy is cheaper, but cheaper is worthless when the answer is wrong. DP pays a small, predictable price for an answer that is always optimal.

Edge Cases

• dp[0] = 0 is the anchor every reachable amount eventually traces back to.
• A coin larger than the current amount is simply not a candidate for that cell.
• An amount with no finite candidate stays at infinity. The impossible preset (coins 3, 5, amount 7) leaves dp[7] at infinity and returns -1; greedy gets stuck after taking 5 with 2 left over.
• On a canonical coin system the heuristic and the table agree. The canonical preset (coins 1, 2, 5, amount 11) has both greedy and DP use three coins — greedy is not always wrong, it is just not always right.
• Returning -1 is a real answer: it is a proof, not a failure to compute. The infinity cell shows there is no combination at all.

Common Mistakes

• Trusting greedy. "Largest coin first" is optimal only for special coin systems; with coins 1, 3, 4 it overshoots. The greedy-fails default exists to make that visible.
• Forgetting the infinity start. If unreachable amounts begin at 0 instead of infinity, every cell looks solvable and the minimum is garbage.
• Adding one to an unsolved source. A candidate is only valid when dp[a - c] is already finite; infinity + 1 is still no solution, not a cheaper one.
• Confusing "minimum coins" with "number of ways." This lesson counts the fewest coins. Counting how many distinct combinations make an amount is a different DP with a different recurrence.
• Tracing forward. The coins are recovered backward from the final amount, following the winning coin recorded at each cell.

A Note on Simplification

This is the textbook minimum-coins problem on a small, friendly set of denominations, built to show greedy failing and DP succeeding side by side. Real currency systems are usually designed so greedy works, which is exactly why the failure case feels surprising — you rarely meet it at a cash register. The code already stores one row, dp[0..amount]; production solvers simply skip the explicit number line, and the walking token and arcs here are teaching scaffolding, not how you would ship it. Treat this as an explainer for the idea, not a drop-in implementation.