Q17: Coin Change (Dynamic Programming)
Find the minimum number of coins needed to make up a given amount using bottom-up dynamic programming.
Bottom-Up DP Coin Change
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (let coin of coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(coinChange([1, 2, 5], 11)); // 3 (5 + 5 + 1)💡 dp[i] stores min coins needed for amount i. Iterates through all available coins to find minimum coin combinations step by step.
Key Takeaways
- Dynamic Programming lookup table array initialized to
Infinity. - State transition:
dp[i] = min(dp[i], dp[i - coin] + 1).
Knowledge Check
What value does coinChange return if the target amount cannot be made by any coin combination?