Same knapsack, new rule: you may take item i as many times as capacity allows. Coins are the usual contest costume — denominations coins[j], make amount A, unlimited supply of each coin.
Two scores:
- Max value unbounded knapsack (the 0/1 table with the inner loop reversed).
- Min coins (LeetCode Coin Change):
dp[x]= fewest coins summing tox, or impossible.
The second one is what you will code in the arena. Greedy (always the largest coin) is wrong as soon as denominations are ugly: coins 1, 3, 4 and amount 6 — greedy takes 4+1+1 (3 coins); two threes is 2.
function coinChange(coins, amount) {
const inf = amount + 1;
const dp = Array(amount + 1).fill(inf);
dp[0] = 0;
for (let x = 1; x <= amount; x++) {
for (const c of coins) {
if (c <= x) dp[x] = Math.min(dp[x], dp[x - c] + 1);
}
}
return dp[amount] >= inf ? -1 : dp[amount];
}dp[0] = 0 (zero coins make zero). Unreachable amounts stay at the sentinel; return -1 if dp[amount] never dropped. Order of coins does not matter for correctness of this complete-inner-loop form.
A related problem is combination count (number of ways). Then the *outer* loop must be the coins, so [1,2] and [2,1] are not double-counted as different ways — unless the statement wants permutations. Read the statement. Min-coins does not care about order.
Checks 0/2