9.3 Unbounded Knapsack / Coin Change

Demo: Coin Change — LC 322 (Medium — Amazon/Google High)

Statement (Demo): Given coins and an amount, return the fewest coins that make up the amount, or -1 if impossible. Example: coins=[1,2,5], amount=11 → 3 (5 + 5 + 1) | ⚡ coins.length ≤ 12, amount ≤ 10⁴

Approach: dp[a] = the fewest coins for amount a. For each coin, update a going forwards — forwards means reuse is allowed (compare with the backwards loop in 9.2).

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (const coin of coins)
    for (
      let a = coin;
      a <= amount;
      a++ // forwards = unbounded
    )
      dp[a] = Math.min(dp[a], dp[a - coin] + 1);
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Complexity: Time O(n · amount), Space O(amount)