Problem
Given coins of different denominations and an amount, return the fewest coins needed to make that amount. Return -1 if impossible.
Example
Input: coins = [1,2,5], amount = 11
Output: 3
5 + 5 + 1.Solution
DP. dp[i] = min coins for amount i. dp[i] = min(dp[i – coin] + 1) for each coin.
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 dp[amount] if dp[amount] <= amount else -1function 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 ? dp[amount] : -1;
}int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int c : coins) {
if (c <= i) dp[i] = min(dp[i], dp[i - c] + 1);
}
}
return dp[amount] <= amount ? dp[amount] : -1;
}public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
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 ? dp[amount] : -1;
}Complexity
- Time: O(amount * coins)
- Space: O(amount)
Explanation
Build up from amount 0. For each amount, try every coin denomination. If dp[amount] is still the initial value, no combination works.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?