#322
Coin Change
Medium Unbounded knapsack (min coins)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the fewest coins needed to make an amount using unlimited coins of given denominations, or -1 if impossible.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: fewest coins to make an amount.
Why this works: dp[a] = 1 + min over coins of dp[a - coin]. Greedy can fail; DP tries every last coin.
Example: coins [1, 2, 5], amount 11
dp[11] = dp[6] + 1 = (dp[1] + 1) + 1 = 3 (5 + 5 + 1)✦Hints open one at a time
dp[a] = fewest coins for amount a.
dp[a] = 1 + min over coins c of dp[a − c].
Greedy (largest coin first) fails, e.g. coins {1, 3, 4} and amount 6.
↗Approach
Fill dp from 1 to amount with "infinity" (amount + 1) as the start value. Each coin may be reused, so loop amounts upwards.
</>Solution (Java)
import java.util.*;
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // safe "infinity"
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int c : coins) {
if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}!Common mistake
Using Integer.MAX_VALUE as infinity and then adding 1 — it overflows to negative.
Complexity
- Time: O(amount · coins).
- Space: O(amount).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon