凑零钱问题

问题

给定不同面额的硬币数组 coins 和一个总金额 amount，计算凑成总金额所需的最少硬币数。如果无法凑成，返回 -1。

示例：

• 输入：coins = [1, 2, 5], amount = 11
• 输出：3（5 + 5 + 1）

解答

动态规划解法

/**
 * 凑零钱问题 - 动态规划
 * @param {number[]} coins - 硬币面额数组
 * @param {number} amount - 目标金额
 * @return {number} - 最少硬币数，无法凑成返回 -1
 */
function coinChange(coins, amount) {
  // dp[i] 表示凑成金额 i 所需的最少硬币数
  // 初始化为 amount + 1（不可能的值，相当于无穷大）
  const dp = new Array(amount + 1).fill(amount + 1);
  
  // 金额 0 需要 0 个硬币
  dp[0] = 0;
  
  // 遍历每个金额
  for (let i = 1; i <= amount; i++) {
    // 尝试每种硬币
    for (const coin of coins) {
      // 当前硬币面额不超过目标金额
      if (coin <= i) {
        // 状态转移：不用这枚硬币 vs 用这枚硬币
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  
  // 如果 dp[amount] 没被更新过，说明无法凑成
  return dp[amount] > amount ? -1 : dp[amount];
}

// 测试
console.log(coinChange([1, 2, 5], 11)); // 3 (5+5+1)
console.log(coinChange([2], 3));        // -1
console.log(coinChange([1], 0));        // 0
console.log(coinChange([1, 2, 5], 100)); // 20 (5*20)

记忆化递归解法

/**
 * 凑零钱问题 - 记忆化递归
 */
function coinChangeMemo(coins, amount) {
  const memo = new Map();
  
  function dp(remain) {
    // 已计算过，直接返回
    if (memo.has(remain)) return memo.get(remain);
    
    // 基础情况
    if (remain === 0) return 0;
    if (remain < 0) return -1;
    
    let minCoins = Infinity;
    
    // 尝试每种硬币
    for (const coin of coins) {
      const subResult = dp(remain - coin);
      // 子问题有解
      if (subResult !== -1) {
        minCoins = Math.min(minCoins, subResult + 1);
      }
    }
    
    // 缓存结果
    const result = minCoins === Infinity ? -1 : minCoins;
    memo.set(remain, result);
    return result;
  }
  
  return dp(amount);
}

// 测试
console.log(coinChangeMemo([1, 2, 5], 11)); // 3

BFS 解法

/**
 * 凑零钱问题 - BFS（求最短路径）
 */
function coinChangeBFS(coins, amount) {
  if (amount === 0) return 0;
  
  const visited = new Set([0]);
  const queue = [0];
  let steps = 0;
  
  while (queue.length > 0) {
    steps++;
    const size = queue.length;
    
    for (let i = 0; i < size; i++) {
      const curr = queue.shift();
      
      for (const coin of coins) {
        const next = curr + coin;
        
        if (next === amount) return steps;
        if (next < amount && !visited.has(next)) {
          visited.add(next);
          queue.push(next);
        }
      }
    }
  }
  
  return -1;
}

// 测试
console.log(coinChangeBFS([1, 2, 5], 11)); // 3

关键点

• 状态定义：dp[i] 表示凑成金额 i 所需的最少硬币数
• 状态转移：dp[i] = min(dp[i], dp[i - coin] + 1)，对每种硬币取最小值
• 初始化：dp[0] = 0，其余初始化为不可能的大值
• 时间复杂度：O(amount × n)，n 为硬币种类数
• 无解判断：最终值仍为初始大值时返回 -1