Dynamic Programming — Coin Change
↗ LeetCode: Coin Change · Medium · pattern chapter →
Given coins (unbounded supply of each) and amount, return the minimum number of coins that sum to amount, or -1 if impossible.
Example 1 — coins=[1,2,5], amount=11 → 3 (5+5+1) Example 2 — coins=[2], amount=3 → -1Example 3 — coins=[1], amount=0 → 0
Constraints — 1 ≤ #coins ≤ 12; 0 ≤ amount ≤ 10⁴. Brute recursion tries every coin at every amount — O(coins^amount) ≈ 12^10000 for max input (dies before universe end). Bottom-up DP is O(amount·|coins|) = 10⁴·12 ≈ 10⁶ ops = <10 ms.
Interview timer00:00
Approach 1 — Brute force recursion
Intuition. f(rem) = 1 + min(f(rem - c)) over all coins. Base: f(0) = 0; f(<0) = ∞.
int coinChangeBrute(int[] coins, int amount) {
int r = rec(coins, amount);
return r == Integer.MAX_VALUE ? -1 : r;
}
int rec(int[] coins, int rem) {
if (rem == 0) return 0;
if (rem < 0) return Integer.MAX_VALUE;
int best = Integer.MAX_VALUE;
for (int c : coins) {
int r = rec(coins, rem - c);
if (r != Integer.MAX_VALUE) best = Math.min(best, r + 1);
}
return best;
}Complexity — Time O(k^amount); Space O(amount) stack. TLE at amount=10⁴.
Approach 2 — Memoized recursion (top-down DP)
Insight from brute. Same subproblem rec(rem) is called exponentially. Cache.
int coinChangeMemo(int[] coins, int amount) {
Integer[] memo = new Integer[amount + 1];
int r = rec(coins, amount, memo);
return r == Integer.MAX_VALUE ? -1 : r;
}
int rec(int[] coins, int rem, Integer[] memo) {
if (rem == 0) return 0;
if (rem < 0) return Integer.MAX_VALUE;
if (memo[rem] != null) return memo[rem];
int best = Integer.MAX_VALUE;
for (int c : coins) {
int r = rec(coins, rem - c, memo);
if (r != Integer.MAX_VALUE) best = Math.min(best, r + 1);
}
return memo[rem] = best;
}Complexity — Time O(amount · k); Space O(amount).
Approach 3 — Bottom-up DP (tabulation)
Insight from memo. Iterate w from 1 to amount. dp[w] = 1 + min(dp[w - c]) for feasible c.
Trap. Use amount + 1 as the "unreachable" sentinel — Integer.MAX_VALUE + 1 wraps to negative.
int coinChange(int[] coins, int amount) {
int sentinel = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, sentinel);
dp[0] = 0;
for (int w = 1; w <= amount; w++)
for (int c : coins)
if (c <= w) dp[w] = Math.min(dp[w], dp[w - c] + 1);
return dp[amount] == sentinel ? -1 : dp[amount];
}Complexity — Time O(amount · k); Space O(amount). Optimal.
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Brute recursion | O(k^amount) | O(amount) |
| Memoized | O(amount · k) | O(amount) |
| Bottom-up tabulation | O(amount · k) | O(amount) |
When to use which
- Cold interview → brute → memo → table.
- BFS variant → BFS layer = fewest coins; also O(amount · k). Sometimes faster in practice.
Related problems
- Coin Change II — count the ways, not the min
- Combination Sum IV — same skeleton with ordered sequences
- Perfect Squares — coins = square numbers
- Minimum Cost For Tickets — variant with day-based DP