Coin Change Problem — Why Greedy Fails for [1,3,4] Sets
Greedy picks 3 coins for amount 6 with [1,3,4]; DP finds 2.
- Dynamic programming solves coin change by reusing subproblem results, guaranteeing each state is computed once
- Two main variants: minimum coins (unbounded knapsack) and count of ways (combinations, not permutations)
- Time: O(amount * len(coins)) — loop amount for each coin
- Space: O(amount) via 1D array; can be further optimised but not below O(amount)
- Greedy fails for coin systems like [1,3,4], amount=6 (greedy gives 3 coins, optimal is 2)
- Production reality: This isn't just an interview puzzle — payment systems, ticket vending machines, and change-dispensing firmware solve this daily
Every payment system, vending machine firmware, and change-dispensing ATM in the world is quietly solving a version of this problem. When a cashier's drawer runs low on quarters, the register software recalculates optimal change combinations on the fly. When a cryptocurrency exchange breaks a large order into smaller fills, it's optimizing a coin-change variant under the hood. This isn't an academic puzzle — it's load-bearing infrastructure.
The naive approach — try every possible combination recursively — collapses catastrophically at scale. With just 10 coin types and a target of 1000, the recursion tree explodes into millions of redundant sub-problems. The same sub-problems get solved over and over, burning CPU time you'll never get back. Dynamic Programming eliminates that waste entirely by guaranteeing each sub-problem is solved exactly once and its result reused. That's the contract DP makes with you.
By the end of this article you'll be able to implement both the minimum-coins variant and the count-of-ways variant from scratch in Java, explain the recurrence relation cold, optimize from O(amount · coins) space down to O(amount), handle every edge case that trips people up in production and in interviews, and articulate the difference between the two DP approaches well enough to teach it to someone else. Let's build this up piece by piece.
What is Coin Change? — Plain English
The Coin Change problem: given a set of coin denominations and a target amount, find the minimum number of coins needed to make that amount. Coins can be reused any number of times (unbounded). Greedy doesn't always work — with coins [1, 3, 4] and amount 6, greedy picks 4+1+1=3 coins but the optimal is 3+3=2 coins.
This is the classic unbounded knapsack / complete knapsack problem. Dynamic programming builds the answer bottom-up: first solve for amount 0 (trivial: 0 coins), then for amount 1, 2, ... up to the target, reusing already-computed results.
How Coin Change Works — Step by Step
Define dp[amount] = minimum number of coins to make 'amount'.
- Initialize dp[0] = 0 (zero coins needed for amount 0).
- Initialize dp[1..target] = infinity (not yet reachable).
- For each amount from 1 to target:
- For each coin denomination c:
- If c <= amount and dp[amount - c] is not infinity:
- dp[amount] = min(dp[amount], dp[amount - c] + 1)
- Return dp[target]. If still infinity, return -1 (impossible).
Time complexity: O(amount * len(coins)). Space: O(amount).
Worked Example — Tracing the Algorithm
Coins = [1, 3, 4]. Target = 6.
Initialize: dp = [0, INF, INF, INF, INF, INF, INF]
amount=1: try coin 1: dp[0]+1=1. dp[1]=1. dp = [0, 1, INF, INF, INF, INF, INF]
amount=2: try coin 1: dp[1]+1=2. dp[2]=2. dp = [0, 1, 2, INF, INF, INF, INF]
amount=3: try coin 1: dp[2]+1=3. try coin 3: dp[0]+1=1. min(3,1)=1. dp[3]=1. dp = [0, 1, 2, 1, INF, INF, INF]
amount=4: try coin 1: dp[3]+1=2. try coin 3: dp[1]+1=2. try coin 4: dp[0]+1=1. min=1. dp[4]=1. dp = [0, 1, 2, 1, 1, INF, INF]
amount=5: try coin 1: dp[4]+1=2. try coin 3: dp[2]+1=3. try coin 4: dp[1]+1=2. min=2. dp[5]=2. dp = [0, 1, 2, 1, 1, 2, INF]
amount=6: try coin 1: dp[5]+1=3. try coin 3: dp[3]+1=2. try coin 4: dp[2]+1=3. min=2. dp[6]=2. dp = [0, 1, 2, 1, 1, 2, 2]
Answer: dp[6] = 2 coins. The combination is coin 3 + coin 3.
Java Implementation — Minimum Number of Coins
Here's a clean Java implementation of the bottom-up DP for Coin Change. It uses a 1D array to minimise space, handles the sentinel overflow issue, and returns -1 when impossible.
Edge Cases and Common Traps
Edge cases that break naive implementations:
- Amount = 0: result is 0 coins. Ensure dp[0]=0 and loop starts at 1.
- Impossible amount: e.g., coins={2}, amount=3. Return -1 correctly.
- Large coin value: if coin > amount, skip it inside the loop to avoid index out of bounds. Use
if (coin <= a)guard. - Unsorted coins: algorithm handles any order, but sorted coins may give minor cache benefits.
- Very large amounts (≥10^6): O(amount*coins) becomes heavy. Consider greedy for canonical sets or heuristic pruning.
Coin Change II: Count Number of Combinations
The second variant: count the number of distinct ways to make the amount using unlimited coins. Order does not matter — (1,2) and (2,1) count as one combination.
Recurrence: dp[a] += dp[a - coin] (for each coin), but careful: outer loop must be over coins, inner loop over amounts to avoid counting permutations as separate combinations.
Initialize dp[0] = 1 (one way: use no coins). For each coin, for each amount from coin to target: dp[a] += dp[a - coin].
Example: coins={1,2}, amount=4 → combinations: {1+1+1+1}, {1+1+2}, {2+2} → 3 ways.
| Aspect | Minimum Coins (Min) | Number of Ways (Count) | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|---|---|---|
| DP array meaning | dp[a] = min coins for amount a | dp[a] = number of distinct ways to make amount a | memo map from amount to result | dp array from 0 to target |
| Recurrence | dp[a] = min(dp[a], dp[a-coin]+1) | dp[a] += dp[a-coin] (with proper loop order) | same as bottom-up but recursive | same as left |
| Time complexity | O(amount × coins) | O(amount × coins) | O(amount × coins) | O(amount × coins) |
| Space complexity | O(amount) | O(amount) | O(amount) + recursion stack | O(amount) |
| Ease of implementation | Straightforward iterative | Straightforward with correct loop order | Requires handling recursion depth | Simple loops |
| Risk of overflow | Sentinel overflow (use amount+1) | Count overflow (use modulo) | Stack overflow for large amounts | None, but array size may be large |
| Use case | Minimum change, payment systems | Game mechanisms, probability | When amount is small or coins limited | General purpose, production |
Key Takeaways
- Coin Change finds the minimum coins for a target amount using unbounded DP.
- dp[a] = min coins to make amount a. Recurrence: min over all coins c of dp[a-c]+1.
- Initialize dp[0]=0 and dp[1..target]=amount+1 (not Integer.MAX_VALUE). Return -1 if dp[target] remains sentinel.
- Greedy fails because locally optimal choices block globally optimal combinations.
- Time: O(amount * coins). Space: O(amount). Count ways variant: dp[0]=1, outer coin loop, inner amount loop.
- Edge cases: amount=0→0, impossible→-1, guard coin ≤ amount, avoid overflow by using amount+1 as sentinel.
Common Mistakes to Avoid
- Using greedy for arbitrary coin denominations
Symptom: Incorrect (suboptimal) change dispensed, leading to financial loss or customer complaints.
Fix: Implement DP instead. For production, validate that the coin set is canonical (greedy-safe) via brute-force for all amounts up to some threshold. - Using Integer.MAX_VALUE as INF and then adding 1
Symptom: Overflow produces negative values in the dp array, resulting in zero or negative coin counts. Non-deterministic crashes.
Fix: Use amount + 1 as sentinel. This guarantees no overflow because max coin count cannot exceed amount. - Wrong loop order in count combinations variant
Symptom: Count is larger than expected because permutations are counted as separate ways (e.g., (1,2) and (2,1) both counted).
Fix: Outer loop over coins, inner loop over amounts from coin to target. That ensures each combination is counted once. - Forgetting that coins can be reused (unbounded), leading to 0/1 knapsack logic
Symptom: Result is -1 for amounts that should be reachable, or result is larger than optimal because each coin used at most once.
Fix: Ensure the inner loop iterates over all coins for each amount (unbounded). For 0/1 knapsack, iterate amounts in reverse to prevent reuse.
Interview Questions on This Topic
- QWhy does the greedy approach fail for the coin change problem?JuniorReveal
- QWhat is the recurrence relation for the minimum coin change DP?Mid-levelReveal
- QHow would you modify the solution to return the actual coins used, not just the count?SeniorReveal
- QExplain the difference between the minimum coins variant and the count of ways variant.Mid-levelReveal
- QWhat happens if you reverse the loop order in the count ways DP?SeniorReveal
Frequently Asked Questions
Why doesn't the greedy approach always work for coin change?
Greedy always picks the largest coin that fits the remaining amount. With coins [1, 3, 4] and amount 6, greedy picks 4 then 1+1 = 3 coins. But 3+3 uses only 2 coins. Greedy fails when skipping the largest coin now allows a more efficient combination later. DP considers all possibilities and guarantees the optimal.
How is this different from the 0/1 knapsack?
In 0/1 knapsack, each item can be used at most once. In coin change, each coin denomination can be used unlimited times (unbounded knapsack). The DP iteration direction differs: coin change iterates amounts forward (dp[a] can reference dp[a-coin] which was already updated in the same pass, allowing multiple uses of the same coin). 0/1 knapsack iterates in reverse to prevent reuse.
How do you count the total number of ways to make change (not the minimum)?
Change the DP meaning: dp[a] = number of ways to make amount a. Initialize dp[0]=1, all others 0. For each coin, for each amount from coin to target: dp[a] += dp[a-coin]. The outer loop should iterate over coins (not amounts) to avoid counting the same combination in different orders.
What is the time and space complexity of DP solution?
Time: O(amount * len(coins)) because we loop through each amount and try each coin. Space: O(amount) for the 1D dp array. If we want to reconstruct the coins used, we need an additional array of the same size to store which coin was used.
Can we optimise space further than O(amount)?
No, because the DP recurrence dp[a] depends on dp[a-coin] which can be up to 'amount' apart. We need to store all values up to amount. However, we can use a 1D array (O(amount)) which is already optimal. Using a 2D array (O(amount*coins)) would be wasteful.
That's Dynamic Programming. Mark it forged?
3 min read · try the examples if you haven't