Given coin denominations and a target amount, return the minimum number of coins that sum to the amount, or -1 if impossible.
This is a bottom-up DP: dp[i] is the fewest coins to make amount i. Initialize dp[0] = 0 and the rest to "infinity", then for each amount try every coin, taking dp[i] = min(dp[i], dp[i - coin] + 1). A greedy "largest coin first" is wrong for arbitrary denominations. O(amount * coins).
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
java.util.Arrays.fill(dp, amount + 1);
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];
}function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let i = 1; i <= amount; i++)
for (const c of coins)
if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}def coin_change(coins, amount):
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i - c] + 1)
return -1 if dp[amount] > amount else dp[amount]Coin change models resource-optimization problems (making change, cutting stock, minimal-unit packing) and is the canonical unbounded-knapsack DP.
A candidate greedily picks the largest coin each time and fails for coins [1,3,4], amount 6 (returns 3 instead of 2). Why?