MediumFewest coins to make an amount — bottom-up DP, not greedy.
Given an array of coin denominations and a target amount, return the fewest number of coins needed to make up that amount. If it cannot be made, return −1. You have an unlimited supply of each coin.
Walkthrough
try:
Fewest coins to make the amount. Build up dp[0..amount]; dp[a] uses dp[a−coin] + 1.
coins125
0
1
2
3
4
5
6
7
8
9
10
11
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
dp[a] (solving)dp[a−coin] (source)reachable
1
function coinChange(coins, amount) {
2
const dp = Array(amount + 1).fill(Infinity);
◄
3
dp[0] = 0;
4
for (let a = 1; a <= amount; a++) {
5
for (const coin of coins) {
6
if (coin <= a) {
7
dp[a] = Math.min(dp[a], dp[a-coin] + 1);
8
}
9
}
10
}
11
return dp[amount] === Infinity ? -1 : dp[amount];
12
}
step 0 / 46
line 2
dp[a] = fewest coins to make a
Fill dp so dp[a] is the minimum number of coins summing to a. Start everything at ∞ (unreachable).
Intuition
Greedy (always take the biggest coin) is WRONG here: with coins [1,3,4] and amount 6, greedy gives 4+1+1 = 3 coins, but 3+3 = 2 is better. You must consider every option.
Build up from small amounts: dp[a] = the fewest coins to make amount a. Start dp[0] = 0 (zero coins make zero) and everything else at ∞ (unreachable so far).
To make amount a, try each coin as the LAST one used: that costs dp[a − coin] + 1. Take the cheapest across all coins.
If dp[amount] is still ∞ at the end, no combination works → return −1.
The algorithm
01Fill dp[0..amount] with ∞ and set dp[0] = 0.
02For each amount a from 1 to amount, and each coin ≤ a: