coin-change.ts

/**
 * 322. Coin Change  (Medium)
 * Link: https://leetcode.com/problems/coin-change/
 *
 * Given coin denominations and an amount, return the fewest coins needed to
 * make up that amount, or -1 if it cannot be made. You have an infinite supply
 * of each coin.
 *
 * Example:
 *   Input:  coins = [1, 2, 5], amount = 11
 *   Output: 3            // 5 + 5 + 1
 *
 * Approach:
 *   Bottom-up DP. dp[a] = fewest coins to make amount `a`. Initialize to a
 *   sentinel (amount + 1 = "infinity"), dp[0] = 0. For each amount, try every
 *   coin that fits and take 1 + dp[a - coin]. This is the unbounded-knapsack
 *   style min recurrence.
 *
 * Time:  O(amount * coins.length)
 * Space: O(amount)
 */
export function coinChange(coins: number[], amount: number): number {
  const INF = amount + 1;
  const dp = new Array<number>(amount + 1).fill(INF);
  dp[0] = 0;

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) {
        dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
      }
    }
  }

  return dp[amount] === INF ? -1 : dp[amount];
}