零钱兑换

/*
 * 题目：零钱兑换
 * 要求：输入正整数面额数组 coins 与非负整数金额 amount；每种硬币可无限次使用，返回恰好凑出 amount 的最少硬币数，无法凑出返回 -1；amount=0 返回 0。
 * 示例：coins=[1,3,4]、amount=6 返回 2（3+3），而按最大面额优先会使用 3 枚。
 */
function coinChange(coins, amount) {}
console.log(coinChange([1, 2, 5], 11)); // 预期：3
console.log(coinChange([2], 3)); // 预期：-1
console.log(coinChange([1, 3, 4], 6)); // 预期：2
console.log(coinChange([], 0)); // 预期：0

function coinChange(coins, amount) {
  if (!Number.isInteger(amount) || amount < 0)
    throw new RangeError("amount must be a non-negative integer");
  const normalized = [...new Set(coins)];
  if (!normalized.every((coin) => Number.isInteger(coin) && coin > 0))
    throw new RangeError("coins must be positive integers");
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let value = 1; value <= amount; value += 1)
    for (const coin of normalized)
      if (coin <= value && dp[value - coin] !== Infinity)
        dp[value] = Math.min(dp[value], dp[value - coin] + 1);
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// 三组以上可直接运行的验证。
console.log(coinChange([1, 2, 5], 11)); // 预期：3
console.log(coinChange([2], 3)); // 预期：-1
console.log(coinChange([1, 3, 4], 6)); // 预期：2
console.log(coinChange([], 0)); // 预期：0