Coin Change
Problem
coins, each available in unlimited
quantity. Return the fewest coins whose values add up exactly to
amount, or -1 if that amount cannot be formed.coins=[1,2,5], amount=11Output3 (5+5+1)coins=[2], amount=3Output-1coins=[1], amount=0Output01 ≤ coins.length ≤ 12 · 1 ≤ coins[i] ≤ 231-1 · 0 ≤ amount ≤ 104
Try it yourself
class Solution {
public int coinChange(int[] coins, int amount) {
}
}
[1,3,4], 6. Instead, the
last coin used is some c, so
best(a) = 1 + minc best(a - c) — and there are only
amount+1 distinct sub-amounts.Instinct Choose items to hit or stay under a target sum (can it be done, best value, fewest items, how many ways) - index a DP array by the remaining capacity.
Memory hack Once? Walk back. Many? Walk forward. Each item used at most once loops capacity downward; reusable items loop it upward.
Open the Knapsack DP guide →Approaches
Brute ForcePlain Recursion over Last Coin
O(kA)Space O(A)For remaining amount rem, try every coin as the next one and recurse
on rem - c; keep the minimum. With k coins and depth up to
A = amount (coin 1), the tree has up to kA nodes
because sub-amounts repeat endlessly.
public int coinChange(int[] coins, int amount) { if (amount == 0) return 0; if (amount < 0) return -1; int best = Integer.MAX_VALUE; for (int c : coins) { int sub = coinChange(coins, amount - c); if (sub >= 0) best = Math.min(best, sub + 1); } return best == Integer.MAX_VALUE ? -1 : best; }
Correct, but hopeless for amounts beyond ~30.
BetterTop-Down Memoization
O(k·A)Space O(A)The result depends only on rem, so cache it in
memo[rem] (0 = not computed; real answers for
rem > 0 are ≥ 1 or -1). Each of the
A states loops over k coins once.
public int coinChange(int[] coins, int amount) { return solve(coins, amount, new int[amount + 1]); } private int solve(int[] coins, int rem, int[] memo) { if (rem == 0) return 0; if (rem < 0) return -1; if (memo[rem] != 0) return memo[rem]; int best = Integer.MAX_VALUE; for (int c : coins) { int sub = solve(coins, rem - c, memo); if (sub >= 0) best = Math.min(best, sub + 1); } return memo[rem] = (best == Integer.MAX_VALUE) ? -1 : best; }
Fast, but recursion can go 104 frames deep.
OptimalBottom-Up 1-D Tabulation
O(k·A)Space O(A)Fill dp[0..A] in increasing order with
dp[i] = min(dp[i], dp[i-c] + 1). Use A+1 as
“infinity” (no answer needs more than A coins), which also
avoids MAX_VALUE + 1 overflow. Unlimited reuse is natural here.
public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); // "infinity" dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int c : coins) { if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1); } } return dp[amount] > amount ? -1 : dp[amount]; }
Dry runcoins=[1,3,4], amount=6; cells = dp[0..6]
- init0∞∞∞∞∞∞dp[0] = 0
- i=1,2012i∞∞∞∞only coin 1 fits
- i=30121i∞∞∞dp[0]+1 via coin 3
- i=401211i∞∞dp[0]+1 via coin 4
- i=5012112i∞dp[4]+1 or dp[1]+1
- i=60121122idp[3]+1 = 2 ✔
Same complexity, iterative and cache-friendly — the standard answer.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Plain Recursion over Last Coin | O(kA) | O(A) |
| Better | Top-Down Memoization | O(k·A) | O(A) |
| Optimal | Bottom-Up 1-D Tabulation | O(k·A) | O(A) |
- Greedy by largest coin — not optimal for arbitrary denominations.
- Using
Integer.MAX_VALUEas infinity, then+1→ overflow. - Memo sentinel clash: don't use
-1for both “unknown” and “impossible”.
- Show a greedy counter-example first to justify DP.
- State the recurrence via the last coin; note it's unbounded knapsack (forward loop).
- Contrast with Coin Change II (count ways): swap the loop order to avoid counting permutations.