—
a
Given coin denominations and a target amount, find the fewest coins that sum to it — or -1if it's impossible. A bottom-up DP table over amounts fills each cell with the minimum over every usable coin, exploiting the fact that each denomination can be reused without limit.
Given coins [1, 2, 5] and amount = 11, return the fewest coins summing to 11. Answer: 3 (two 5s and one 1: 5 + 5 + 1). Each denomination can be used any number of times. If no combination reaches the target, return -1.
dp[a] = the minimum coins to make amount a. For every coin c ≤ a, we already know dp[a−c] (a strictly smaller sub-problem), so the best we can do using coin c is dp[a−c] + 1. Take the min over all coins. This is the unbounded-knapsack recurrence: coins can repeat because we re-read the same dparray we're filling.dp[0] = 0 — zero coins needed to reach amount zero. All other cells start at Infinity (unreachable sentinel).c ≤ a and dp[a−c] ≠ Infinity, then dp[a] = min(dp[a], dp[a−c] + 1). Skipping Infinity sources prevents a silent integer-overflow bug.dp[amount]. Still Infinity? Return -1; no combination reaches the target.dp[a−c] for the same pass is exactly what lets a coin be used multiple times.k = number of coin denominations. Space is O(amount) for the 1-D table — far less than the O(amount × k) 2-D table a 0/1-knapsack would need. Top-down memoized DFS reaches the same asymptotic cost but incurs call-stack overhead.
dp[0..11]: dp[0] = 0, all others ∞. We want the minimum coins to reach each amount.function coinChange(coins: number[], amount: number): number {
const dp: number[] = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // base case: 0 coins needed to reach 0
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a && dp[a - c] !== Infinity) {
dp[a] = Math.min(dp[a], dp[a - c] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}amount + 1 filled with Infinityrepresents “not yet reachable.” Setting dp[0] = 0 is the only hard-coded base case; every other answer is derived from it.a from 1 to amount (left to right) guaranteeing that when we compute dp[a], every dp[a−c] is already final. The inner loop tries every coin; the guard c <= a avoids negative indices and the !== Infinity guard prevents a silent wrap-around.dp[a - c] + 1: the minimum coins to reach a - c, plus the one coin c we just decided to use. Math.minkeeps the best option found so far across all coins. Coins are unbounded because we read from the same array being filled — no need for a separate “used” dimension.dp[amount] is still Infinity, no combination of the given coins sums to amount. The ternary converts the sentinel to the problem's required -1.dp[a] loops over all k coins once. O(amount) space for the 1-D table. No recursion overhead; the iterative approach is both faster in practice and easier to bound.parent[a] array recording which coin was chosen at each amount, then walk back from amount to 0.Math.min(dp[a], dp[a-c]+1) to dp[a] += dp[a-c] and seed dp[0] = 1— that's Coin Change II (LC 518).Map<number, number>; same O(amount × k) time but with O(amount) call-stack depth.amount = 0 returns 0 immediately (base case). coins = [2], amount = 3 returns -1 (odd target, only even denomination).| "minimum number of coins/items to reach target" | 1-D DP, forward loop, dp[a] = min(dp[a], dp[a-c]+1) |
| denominations can be reused unlimited times | unbounded knapsack — read dp[a-c] from the current (same) pass |
| "if impossible return -1" | initialize dp with Infinity; check at the end |
| "count ways instead of min coins" | swap min for sum (dp[a] += dp[a-c]), seed dp[0]=1 |
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a && dp[a - c] !== Infinity) {
dp[a] = Math.min(dp[a], dp[a - c] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];coins = [1, 2, 5], amount = 11, what does dp[6] equal after the full table is built?coins = [2], amount = 3. What is returned?dp[0] equals: