Coin Change Problem: How Would You Solve It?
Learn how to solve the coin change (minimum coins) problem with dynamic programming, why greedy fails, and a Python solution.
Expected Interview Answer
The coin change problem (minimum coins to make an amount) is solved with dynamic programming: dp[a] holds the fewest coins needed to make amount a, computed as dp[a] = min(dp[a - coin] + 1) over every coin denomination that fits, with dp[0] = 0 as the base case.
You fill dp for every amount from 1 up to the target, and for each amount you try every coin denomination that does not exceed it, taking whichever choice gives the smallest coin count. Any amount that remains unreachable stays at infinity (or a sentinel value), which signals no valid combination exists once the table is complete. This is an unbounded-knapsack-style problem since each coin denomination can be reused any number of times, so the loop structure iterates amounts outward with an inner loop over coins, not the reverse-iteration trick 0/1 knapsack needs. A closely related variant, counting the number of ways to make an amount rather than the minimum coins, swaps the recurrence to a sum instead of a min and must iterate coins in the outer loop to avoid counting permutations as distinct combinations.
- O(amount * coins) time, straightforward bottom-up table
- Naturally handles arbitrary denominations, not just canonical currency systems
- Detects unreachable amounts cleanly via a sentinel value
- Recurrence generalizes directly to counting combinations
AI Mentor Explanation
A physio deciding the fewest recovery sessions of a few fixed durations needed to hit an exact total rehab-time target works this out amount by amount, from zero minutes up to the target. For each running total, they check every session duration that fits and take whichever leaves the smallest running count of sessions used so far. If a total is impossible to reach exactly with the available durations, it stays marked unreachable rather than getting a false answer. Building this total-by-total table, always looking one session-length back, is precisely the coin-change recurrence.
Step-by-Step Explanation
Step 1
Define the state
dp[a] = fewest coins needed to make amount a; dp[0] = 0, all others start at infinity.
Step 2
Write the recurrence
dp[a] = min(dp[a], dp[a - coin] + 1) for every coin denomination not exceeding a.
Step 3
Fill amounts outward
Compute dp for every amount from 1 to the target, trying all coins at each step (unbounded, coins reusable).
Step 4
Read the result
dp[target] is the answer; if it is still infinity, the amount is unreachable with the given coins.
What Interviewer Expects
- State the min-based recurrence and base case dp[0]=0
- Explain why this is an unbounded knapsack variant (coins reusable)
- Handle the unreachable case correctly (infinity/sentinel, not -1 silently)
- Distinguish "minimum coins" from "number of ways" (min vs sum recurrence, loop order)
Common Mistakes
- Using a greedy largest-coin-first approach, which fails for non-canonical coin systems (e.g. [1,3,4] for amount 6)
- Forgetting to initialize dp[0] = 0 and other entries to infinity
- Confusing the "fewest coins" variant with the "number of combinations" variant's loop order
- Not checking whether the final dp[target] is still unreachable before returning it
Best Answer (HR Friendly)
“Coin change is about finding the minimum number of coins needed to make a target amount, and I solve it by building up an answer for every amount from zero to the target, always checking what the best answer was for a smaller amount after using one more coin. A key thing I always mention is that greedy — always grabbing the biggest coin first — does not work for every set of denominations, so dynamic programming is the safe, general approach.”
Code Example
def coin_change(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for coin in coins:
if coin <= a and dp[a - coin] + 1 < dp[a]:
dp[a] = dp[a - coin] + 1
return dp[amount] if dp[amount] != INF else -1
print(coin_change([1, 3, 4], 6)) # 2 (3 + 3)
print(coin_change([2], 3)) # -1 (unreachable)Follow-up Questions
- How would you count the number of distinct ways to make an amount instead of the minimum coins?
- Why does a greedy approach fail for coin sets like [1, 3, 4] with amount 6?
- How would you also return which coins were used, not just the count?
- How does this problem relate to unbounded knapsack?
MCQ Practice
1. What does dp[a] represent in the minimum-coins formulation?
dp[a] tracks the minimum coin count to reach amount a exactly, built up from smaller amounts.
2. Why does a purely greedy (largest-coin-first) strategy fail for coin change in general?
For [1,3,4] and amount 6, greedy picks 4+1+1 (3 coins) while the optimal answer is 3+3 (2 coins), so greedy is not always optimal.
3. What value should unreachable amounts hold in the dp array before the final check?
Infinity signals no valid coin combination was found, and lets min() comparisons work correctly during the fill.
Flash Cards
What is the coin change min-coins recurrence? — dp[a] = min(dp[a], dp[a-coin] + 1) for every coin <= a; dp[0] = 0.
Why is coin change an unbounded knapsack variant? — Each coin denomination can be reused an unlimited number of times.
Does greedy always solve coin change optimally? — No — it fails for non-canonical denomination sets like [1, 3, 4].
How do you detect an unreachable amount? — If dp[amount] is still infinity/sentinel after filling the table, no combination reaches it.