Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Find the fewest coins summing to amount. The recurrence is dp[a] = 1 + min over coins c of dp[a - c]. Naive recursion is exponential; memoize to O(amount × coins), or build a bottom-up dp[] table from 0 up to amount. Initialize dp[0] = 0 and treat 'unreachable' as infinity so the min stays honest. Return -1 if amount can't be formed.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you reject the tempting greedy, model the problem as min-over-subproblems, handle the 'unreachable = infinity' bookkeeping correctly, and return -1 cleanly.
Where candidates slip
Using a greedy largest-coin-first strategy (wrong for non-canonical coin sets), or letting the ∞ sentinel overflow / relaxing from an unreachable state and corrupting the min.
How to stand out
Disprove greedy with coins=[1,3,4], amount=6 out loud, give the bottom-up table, explain why dp[0]=0 anchors everything, and mention it's unbounded knapsack (vs the 0/1 and counting variants).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewFewest coins to make amountGreedy biggest coin first?TemptingModel as DPExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recursion Over Remaining Amount
1Hint 1Explore hintHide hint
Think about the FIRST coin you place. If you use coin c, what smaller subproblem remains?
2Hint 2Explore hintHide hint
Using coin c leaves you needing 'amount - c' made from the fewest coins. Try every coin and take the best.
3Hint 3Explore hintHide hint
Write coins(rem) = 1 + min over c of coins(rem - c), with coins(0) = 0 and a way to mark 'impossible' for rem < 0 or dead ends.
A · Core idea
Reason about a single coin at a time. To make rem, pick some coin c (≤ rem), pay for it (+1), and recursively make the remaining rem - c with the fewest coins. The answer for rem is the minimum of that over all coins. The base case is coins(0) = 0 — zero coins make zero — and any path that can't reach exactly 0 contributes 'impossible'.
The mental shift: peel one coin, recurse on the remainder. Don't try to plan the whole multiset at once. Just commit to one coin, reduce the target, and let recursion solve the smaller identical problem. Because coins are reusable, every denomination is available again in the subproblem — that's the 'unbounded' part, and it's why we don't shrink the coin list as we recurse.
Why min, not sum or count. We want the fewest coins, so we combine the subproblem answers with min and add 1 for the coin we just spent. Mixing this up with a count (summing the ways) solves a different problem (Coin Change II).
Why we don't ship this. The same rem gets re-solved through countless coin orderings — exponential overlap. Make rem carry a single answer via a cache.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
coins = [1, 2, 5], amount = 6coins(6)
try c=1→coins(5), c=2→coins(4), c=5→coins(1)
branches out2C · Code with teaching comments
Reference implementation previewpublic int coinChange(int[] coins, int amount) { int res = solve(coins, amount); return res == Integer.MAX_VALUE ? -1 : res; } Explore the full codeHide the full code
D · Why it works and complexityO(coinsᵃᵐᵒᵘⁿᵗ) timeO(amount) spaceOpen the invariant and proofExplore the proofHide the proof
The recursion is defined purely by one number — the remaining amount — yet the naive tree recomputes coins(rem) for the same rem over and over via different coin orders. One state variable + heavy overlap is the textbook signal for a clean O(states) DP.
ComplexityO(coinsᵃᵐᵒᵘⁿᵗ) time, O(amount) space — Each call branches into up to `len(coins)` recursive calls and the recursion can go `amount` deep (using 1-valued coins), giving exponential `coins^amount` nodes. Stack depth is O(amount).
E · Edge cases and pitfalls4coins = [2], amount = 3 — Every branch either overshoots or lands on rem=1 with no fitting coin → returns ∞ → -1.Explore edge casesHide edge cases
Edge cases handled
coins = [2], amount = 3Every branch either overshoots or lands on rem=1 with no fitting coin → returns ∞ → -1.
Pitfalls
- Adding 1 to Integer.MAX_VALUE in Java — overflows to a negative number and wins the min wrongly. Guard the ∞ case.
- Shrinking the coin list per recursion — that turns the unbounded problem into 0/1 and undercounts.
- Reaching for greedy largest-coin — provably wrong on [1,3,4], amount=6.
Approach 2 of 3
Top-Down Memoization
1Hint 1Explore hintHide hint
solve(rem) returns the same minimum every time. Where can you store it so it's computed once?
2Hint 2Explore hintHide hint
Add a memo indexed by remaining amount. Check it on entry; fill it before returning.
3Hint 3Explore hintHide hint
memo[rem] = 1 + min over c of solve(rem - c); cache 'impossible' too so dead ends aren't re-explored.
A · Core idea
Keep the peel-one-coin recurrence, but cache solve(rem) so each remaining amount is solved exactly once. A memo array indexed by remainder starts 'uncomputed'; on entry we return the cached value, and we store the result (including 'impossible') before returning.
The mental shift: the answer depends only on the remaining amount. Two different coin orders that both leave rem = 4 have identical futures, so they must yield the same answer. Caching by rem collapses all those duplicate explorations into one. The state space is just the integers 0 .. amount, which is why the linear-ish complexity appears.
Why we cache impossibility too. A remainder that can't be formed (returns ∞) should be remembered as such — otherwise we'd re-discover its impossibility down every path. Storing ∞ in the memo makes dead ends O(1) on repeat.
Why the sentinel must be guarded. In Java, Integer.MAX_VALUE + 1 overflows to a negative number that would falsely win the min. Always check sub != MAX_VALUE before adding 1. Python's float('inf') sidesteps this since inf + 1 == inf.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
coins = [1, 2, 5], amount = 11solve(11)
needs solve(10), solve(9), solve(6)
memo empty3C · Code with teaching comments
Reference implementation previewpublic int coinChange(int[] coins, int amount) { int[] memo = new int[amount + 1]; Arrays.fill(memo, -2); int res = solve(coins, amount, memo); return res == Integer.MAX_VALUE ? -1 : res;Explore the full codeHide the full code
D · Why it works and complexityO(amount × coins) timeO(amount) spaceOpen the invariant and proofExplore the proofHide the proof
This is the same mechanical upgrade as every DP: a correct recursion + a cache keyed on the true state (here, the remaining amount) = optimal time. The hard intellectual work was identifying that 'remaining amount' is the only state that matters — once you see that, the cache writes itself.
ComplexityO(amount × coins) time, O(amount) space — There are `amount + 1` distinct remainders. Each is solved once, doing O(coins) work to scan denominations → O(amount × coins) time. The memo plus recursion stack is O(amount).
E · Edge cases and pitfalls5amount = 0 — solve(0) returns 0 immediately — zero coins, no recursion.Explore edge casesHide edge cases
Edge cases handled
amount = 0solve(0) returns 0 immediately — zero coins, no recursion.coins = [2], amount = 3solve(3)→solve(1)→solve(-1)=∞; memo caches ∞ so it's not recomputed, final -1.
Pitfalls
- Picking a sentinel that collides with 0 or -1 — both are meaningful here, so use -2 (or a boolean 'computed' array).
- Forgetting to memoize the impossible (∞) result — re-explores dead ends.
- Java overflow from MAX_VALUE + 1 — always guard before incrementing.
Approach 3 of 3 · Optimal
Bottom-Up — dp[] Table From 0 to amount (Optimal)
1Hint 1Explore hintHide hint
Instead of recursing down from amount, can you compute the best for 1, then 2, ... up to amount, reusing earlier answers?
2Hint 2Explore hintHide hint
Make dp[a] = fewest coins to form a. dp[0] = 0; everything else starts at a sentinel ∞ (use amount + 1).
3Hint 3Explore hintHide hint
For each a from 1 to amount and each coin c ≤ a: dp[a] = min(dp[a], dp[a - c] + 1). Answer is dp[amount] unless it's still ∞ → -1.
A · Core idea
Build the answers from the ground up. dp[a] is the fewest coins to make exactly a. Anchor dp[0] = 0, set every other entry to a sentinel meaning 'unreachable', then for each amount a try every coin c: if using c is legal (c <= a) and dp[a - c] is reachable, relax dp[a] = min(dp[a], dp[a - c] + 1). After the table is full, dp[amount] is the answer — or -1 if it never dropped below the sentinel.
The mental shift: solve every smaller amount first, in order. Because dp[a] only ever looks down at dp[a - c] for positive c, processing amounts in increasing order guarantees every dependency is already final when you need it. No recursion, no stack — just a clean sweep. This is the same dependency-ordering insight as Climbing Stairs, now over a 1D table indexed by money instead of stairs.
Why `amount + 1` is a perfect ∞. The most coins you could ever need is amount (all 1-valued coins). So amount + 1 is strictly larger than any real answer, it never overflows on addition, and the final test dp[amount] > amount cleanly detects 'impossible' without a separate boolean.
Why dp[0] = 0 is load-bearing. Every reachable amount ultimately traces back to dp[0] through a chain of +1s. If you left dp[0] at ∞, no amount could ever be relaxed and everything would report impossible. That single anchored cell is what makes the whole table meaningful.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
coins = [1, 2, 5], amount = 11Array state
init
dp[0]=0, rest = ∞
3C · Code with teaching comments
D · Why it works and complexityO(amount × coins) timeO(amount) spaceOpen the invariant and proofExplore the proofHide the proof
Coin Change is unbounded knapsack: each coin reusable, optimizing a count. The bottom-up table is the canonical form — and the inner 'min over items, +1' relaxation generalizes directly. Swap min→count-sum and ∞→0 and the very same loops solve Coin Change II; swap +1→+cost and you get minimum-cost variants; the shape is everywhere.
ComplexityO(amount × coins) time, O(amount) space — Outer loop runs `amount` times, inner loop scans all coins → O(amount × coins) time. A single dp array of size amount + 1 → O(amount) space, with no recursion stack.
E · Edge cases and pitfalls6amount = 0 — Loop body never runs; dp[0] = 0 is returned directly — zero coins for zero.Explore edge casesHide edge cases
Edge cases handled
amount = 0Loop body never runs; dp[0] = 0 is returned directly — zero coins for zero.coins = [2], amount = 3dp[1] and dp[3] stay at the sentinel (4 > 3) → returns -1, the impossible case.
Pitfalls
- Initializing the sentinel to Integer.MAX_VALUE — dp[a - c] + 1 overflows; use amount + 1 instead.
- Forgetting the c <= a guard — negative index into dp.
- Returning dp[amount] without the > amount check — leaks the sentinel instead of -1.
- Confusing this with the count variant (Coin Change II), where loop order matters and you sum instead of min.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0; for (int a = 1; a <= amount; a++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Greedy largest-coin-first
Greedy is optimal only for canonical coin systems. On coins=[1,3,4], amount=6 it takes 4+1+1 (3 coins) but 3+3 (2 coins) is better. DP is mandatory.
Explore the code comparisonHide the code comparison
Greedy largest-coin-first
Greedy is optimal only for canonical coin systems. On coins=[1,3,4], amount=6 it takes 4+1+1 (3 coins) but 3+3 (2 coins) is better. DP is mandatory.
Don't write this
count = 0
for c in sorted(coins, reverse=True):
count += amount // c
amount %= c
return countWrite this instead
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] <= amount else -12Sentinel overflow on +1
If 'unreachable' is Integer.MAX_VALUE, then dp[a - c] + 1 overflows to Integer.MIN_VALUE and falsely wins the min, corrupting the table.
Explore the code comparisonHide the code comparison
Sentinel overflow on +1
If 'unreachable' is Integer.MAX_VALUE, then dp[a - c] + 1 overflows to Integer.MIN_VALUE and falsely wins the min, corrupting the table.
Don't write this
Arrays.fill(dp, Integer.MAX_VALUE);
// ...
dp[a] = Math.min(dp[a], dp[a - c] + 1);Write this instead
Arrays.fill(dp, amount + 1);
// ...
dp[a] = Math.min(dp[a], dp[a - c] + 1);3Forgetting the unreachable check
If dp[amount] never improved past the sentinel, the amount can't be formed and you must return -1, not the sentinel value itself.
Explore the code comparisonHide the code comparison
Forgetting the unreachable check
If dp[amount] never improved past the sentinel, the amount can't be formed and you must return -1, not the sentinel value itself.
Don't write this
return dp[amount];Write this instead
return dp[amount] > amount ? -1 : dp[amount];Revise
Carry the pattern into the interview
Pattern to remember
Unbounded knapsack — min coins (bottom-up DP)
Code pattern to memorize
dp[0] = 0; dp[a] = amount+1 (∞) for a ≥ 1
for a in 1..amount:
for c in coins: if c <= a: dp[a] = min(dp[a], dp[a-c] + 1)
return dp[amount] if dp[amount] <= amount else -1Rules to remember
- 1It's a min, not a count — you want the FEWEST coins, so combine subproblems with
min, adding 1 for the coin you just used. - 2Coins are unbounded: you may reuse a denomination any number of times, so the inner loop tries every coin at every amount.
- 3Initialize
dp[0] = 0(zero coins make zero) and every other entry to a sentinel ∞ (amount + 1is a safe stand-in). - 4Only relax
dp[a]fromdp[a - c]whendp[a - c]is reachable — adding to ∞ must stay ∞. - 5Return
-1whendp[amount]is still ∞ — greedy 'take the biggest coin' is wrong (fails on coins=[1,3,4], amount=6).
Use this pattern when
- Minimum count of items (with repetition) to reach an exact target
- Unbounded knapsack: each item reusable, optimize count or value
- Building a target value from a fixed set of denominations
- Greedy by largest denomination demonstrably fails on the coin set
Choose another pattern when
- You need the NUMBER OF WAYS to make the amount → Coin Change II (a count DP, order of loops matters)
- Each coin usable at most once → 0/1 knapsack, iterate amount descending
- Denominations are canonical (1,5,10,25) → greedy actually works, no DP needed
- Target is astronomically large with tiny coin set → BFS or number theory, not an O(amount) table
Interview takeaway
Coin Change is the canonical unbounded-knapsack 'minimum' DP. The instant you see 'fewest items to hit a target with reuse', reach for dp[a] = min over items of dp[a - item] + 1, with dp[0] = 0 and ∞ elsewhere. The same skeleton (swap min↔count, ∞↔0) solves Coin Change II, Perfect Squares, and Minimum Cost problems.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical unbounded-knapsack 'minimum' DP. Recognize it whenever you must reach an exact target using reusable items while optimizing a count or cost. Same skeleton as Coin Change II (count), Perfect Squares, and Minimum Cost For Tickets.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Coin Change IIComing soonCount the NUMBER OF ways, not the minimum coins. Loop coins outer, amount inner, and sum dp[a - c] (loop order prevents counting permutations).
- Perfect SquaresComing soonExactly Coin Change where the 'coins' are 1, 4, 9, 16, … — minimize the count of squares summing to n.
- Combination Sum IVComing soonCount ordered sequences (permutations) summing to target — amount outer, coins inner.
- Minimum Cost For TicketsComing soonSame min-over-options DP, but the 'coins' are passes covering 1/7/30 days at different costs.