You hand over money at a shop and owe 30 cents. You could count out 30 pennies, but you'd never do that — you reach for a quarter and a nickel, just two coins. That instinct, "make the exact amount with the fewest coins," is the whole problem. The only twist is that the coins you're allowed to use are given to you as a set, and they aren't always the friendly 1, 5, 10, 25 you grew up with.
Build it up. Call the target the amount $A$ and the allowed coin values $c_1, c_2, \dots$. The clever move is to solve the small amounts first and reuse them. Let $dp[a]$ mean "the fewest coins that add up to exactly $a$." Start with $dp[0]=0$, because zero coins already make zero. To fill in any other $dp[a]$, try every coin $c$ that isn't bigger than $a$: if you spend that coin, the rest of the bill still needs $dp[a-c]$ coins, so this choice costs $dp[a-c]+1$. Keep the best one.
The recurrence. In one line, $\;dp[a] = 1 + \min_{c \le a} dp[a-c]$, with $dp[0]=0$ and $dp[a]=\infty$ whenever no coin fits. Worked example, coins $\{1,3,4\}$, amount 6: filling left to right gives $dp[1]=1,\ dp[2]=2,\ dp[3]=1,\ dp[4]=1,\ dp[5]=2$, and finally $dp[6]=1+\min(dp[5],dp[3],dp[2])=1+\min(2,1,2)=2$ — two 3s. A greedy grab-the-biggest-coin approach would take the 4 first ($4+1+1$, three coins) and lose. That gap is exactly why we need DP.
Why the order and the cost. We sweep amounts from 1 up to $A$, and for each one we look at every coin, so the work is $O(A \cdot k)$ for $k$ coins, using an $O(A)$ array. Sweeping upward is what lets a coin be reused as many times as we like (it's the "unbounded" knapsack); a 0/1 knapsack would sweep downward to forbid reuse. The $\infty$ sentinel matters too: if $dp[A]$ is still infinite at the end, that amount simply can't be made (try coins $\{2\}$, amount 3). And although the table is fast for everyday amounts, the problem is weakly NP-hard — the runtime grows with the value $A$, not the number of digits in $A$ — so it's "pseudo-polynomial," the same family as 0/1 knapsack.
Try this in the panel above. The controls drive a generic step-by-step trace visualizer, so use it to get fluent at reading an algorithm one move at a time, then map that onto the coin-change pseudocode shown. First, press Play, drop the speed to 0.25×, and walk with ◀ / ▶│ — watch a single pseudocode line light up per step, just as a real DP fills one $dp[a]$ cell at a time. Second, slide n up and press Reset: more elements means more steps, mirroring how a larger amount $A$ makes the coin table longer (the $O(A \cdot k)$ cost). Third, on paper, fill $dp[0..6]$ for coins $\{1,3,4\}$ by hand and confirm you also land on 2 for amount 6 — then convince yourself why greedy fails.
§3 — Complexity Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity
W(n)
Worst case
A(n)
Average case
Step 1 -- Unbounded Knapsack Variant. Coin change is unbounded knapsack: each coin can be used unlimited times. Goal: minimum number of coins summing to amount. dp[amt] = minimum coins for amount amt.
Step 2 -- Recurrence. dp[0]=0. dp[amt] = 1 + min over coins c (dp[amt-c]) for c <= amt. This checks all coins and picks the one that minimizes total count.
Step 3 -- Time O(amount * |coins|) Space O(amount). Two nested loops: outer over amounts (0 to amount), inner over coins. Total: O(amount * |coins|). Space: O(amount) 1D array.
Step 4 -- Traversal Direction. Must traverse amount LEFT-TO-RIGHT (1 to amount) -- each coin can be reused (unbounded). Contrast with 0/1 knapsack which goes RIGHT-TO-LEFT to prevent item reuse.
Step 5 -- BFS Alternative. Model as unweighted graph: node = remaining amount, edges = subtract each coin. BFS from amount to 0 gives minimum coins (minimum hops). BFS: O(amount * |coins|) time, O(amount) space. Same complexity but DP is usually faster in practice.
Step 6 -- Coin Change 2 (Count Ways). Count number of ways to make amount. Change: dp[amt] += dp[amt-c] (not min, but sum). Iterate coins in outer loop and amounts in inner loop to avoid duplicate orderings (combinations not permutations).
Greedy (always use largest coin) fails for arbitrary coin sets. Example: coins=[1,3,4], amount=6. Greedy: 4+1+1=3 coins. Optimal: 3+3=2 coins. Greedy works ONLY for specific coin systems (like standard currency with coins 1,5,10,25).
What is the difference between coin change 1 (minimum coins) and 2 (count ways)? concept+
Minimum coins: dp[amt] = 1 + min(dp[amt-c]). Count ways: dp[amt] += dp[amt-c]. For count ways, iterate coins in outer loop to count combinations (not permutations -- avoid counting [1,2] and [2,1] separately).
Where is coin change used in practice? applied+
Currency exchange systems. Vending machine change dispensing. Network bandwidth allocation (minimum packets). Resource allocation problems. ATM cash dispensing optimization. Making change is a fundamental CS and economics problem.
Is coin change NP-hard? complex+
It's weakly NP-hard, yet very practical. The standard DP runs in O(amount * |coins|), which is PSEUDO-polynomial -- polynomial in the VALUE of amount, not in the number of digits used to write it. If amount were written in unary, that would be polynomial in the input size; but amounts are normally written in binary, where the value grows exponentially with the digit count. So coin change is in the same family as 0/1 knapsack: NP-hard in general, but solvable in pseudo-polynomial time, which is fast for typical amounts.
How to reconstruct which coins were used? nonobv+
Track coin[amt] = which coin was used to achieve dp[amt]. Backtrack: start at amount, subtract coin[amount], move to amount-coin[amount], repeat until 0. Or: during DP, when dp[amt] is updated via coin c, store c as the choice for amt.
What if no valid combination exists? deep+
dp[amount] remains infinity at end: no valid combination. Return -1. Common case: coins=[2], amount=3 (odd amount, only even coin). Must explicitly check and handle this. Also handle amount=0 as base case: return 0 (zero coins, always possible).
§5 — Misconceptions & Errors
Conceptual Misconceptions
✗ Greedy always gives minimum coins.
✓ Greedy fails for arbitrary coin denominations. Use DP. Greedy only optimal for specific coin sets (canonical systems like US coins 1,5,10,25,50,100).
✗ Coin change and 0/1 Knapsack have the same DP.
✓ Coin change = UNBOUNDED knapsack (unlimited coin reuse). 0/1 Knapsack = each item used at most once. Key difference: traversal direction (left-to-right for unbounded, right-to-left for 0/1).
✗ dp[0]=1 for counting ways problem.
✓ dp[0]=1 for counting combinations (one way to make 0: use nothing). dp[0]=0 for minimum coins (0 coins needed for amount 0). Different initializations for different variants.
Implementation Errors
✗ Initializing dp to 0 instead of infinity for minimum coins.
✓ dp initialized to 0 means 'already achievable with 0 coins' -- wrong. Initialize to infinity (or amount+1) so only reachable amounts get updated.
✗ Coin order matters for counting combinations.
✓ For counting ways (combinations not permutations): iterate coins in outer loop, amounts in inner. Swapping loops counts permutations ([1,2] and [2,1] separately), giving wrong count for 'how many ways'.
✗ Assuming all amounts 1 to amount are reachable.
✓ If smallest coin > 1, some amounts may be unreachable. Always check dp[amount] != infinity before returning.