Coin Change
Minimum number of coins to make a target amount. Bottom-up DP, O(amount × |coins|).
dp
Intro
Given coin denominations and a target amount, return the fewest coins needed to make the amount, or -1 if it's impossible.
Key insight
dp[x] = 1 + min over coins c of dp[x - c]. Greedy fails (e.g., {1, 3, 4} and amount 6 — greedy picks 4+1+1, optimal is 3+3).
Approach
- 1dp[0] = 0; dp[x] = +∞ for x > 0.
- 2For x in 1..amount, for each coin c ≤ x: dp[x] = min(dp[x], dp[x - c] + 1).
- 3Return dp[amount] or -1 if it stayed +∞.
Complexity
Time
O(amount × |coins|)
Space
O(amount)
Code
Snippetjava
int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int x = 1; x <= amount; x++)
for (int c : coins)
if (c <= x) dp[x] = Math.min(dp[x], dp[x - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}Pitfalls
- Trying greedy — fails for non-canonical denominations.
- Initial dp value too small — can't represent 'unreachable'.
Variants & follow-ups
- Coin Change II (LC 518) — number of ways