Medium Dynamic Programming
Coin Change
Receives an array of coin denominations and a target amount, and returns the minimum number of coins needed to make that amount, or -1 if it cannot be made with the given coins. It solves this with bottom-up dynamic programming: a table dp[0..amount] tracks the minimum coins needed for every amount from 0 up to the target, seeded with the base case dp[0] = 0. For each amount i from 1 to the target, it tries every coin denomination no larger than i — if using that coin (dp[i - coin] + 1) needs fewer coins than the best found so far for i, dp[i] is updated. Returns dp[amount], or -1 if it stayed unreachable (no combination of the given coins sums exactly to the target).
Visualization
- Input
- Result
Algorithm code
// Coin Change — a single pure function. Receives an array of coin
// denominations and a target amount, and returns the minimum number of coins
// needed to make that amount, or -1 if it cannot be made. Computed via
// bottom-up dynamic programming: dp[i] holds the minimum coins needed for
// amount i, built from the base case dp[0] = 0 by trying every coin at every
// amount from 1 up to the target.
/**
* @param {number[]} coins - available coin denominations
* @param {number} amount - target amount to make
* @returns {number} minimum number of coins to make amount, or -1 if impossible
*/
export function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i += 1) {
for (const coin of coins) {
if (coin > i) continue;
const candidate = dp[i - coin] + 1;
if (candidate < dp[i]) {
dp[i] = candidate;
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}FUNCTION coinChange(coins, amount):
dp ← array of size (amount + 1) filled with INFINITY
dp[0] ← 0
FOR i FROM 1 TO amount:
FOR EACH coin IN coins:
IF coin > i:
CONTINUE
candidate ← dp[i - coin] + 1
IF candidate < dp[i]:
dp[i] ← candidate
IF dp[amount] == INFINITY:
RETURN -1
RETURN dp[amount]