Fewest Coins to Make a Total
Problem
Given coin denominations coins (unlimited supply of each) and an amount, return the fewest coins that sum exactly to the amount, or -1 if impossible.
Input
coins = [1, 2, 5], amount = 11Output
3dp[a] = fewest coins summing to a. dp[0] = 0; dp[a] = min over coins c of dp[a − c] + 1, when a ≥ c.
def coin_change(coins, amount):
INF = amount + 1
dp = [INF] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return -1 if dp[amount] == INF else dp[amount]function coinChange(coins, amount) {
const INF = amount + 1;
const dp = new Array(amount + 1).fill(INF);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
}
}
return dp[amount] === INF ? -1 : dp[amount];
}class Solution {
public int coinChange(int[] coins, int amount) {
int INF = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, INF);
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] == INF ? -1 : dp[amount];
}
}int coinChange(vector<int>& coins, int amount) {
int INF = amount + 1;
vector<int> dp(amount + 1, INF);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int c : coins) {
if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
}
}
return dp[amount] == INF ? -1 : dp[amount];
}