手帐 Blog

主题

复盘 · LC 322 零钱兑换 ​

题目 ​

题意 ​

给定硬币面额数组 coins 和总金额 amount，每种硬币数量无限，求凑成 amount 的最少硬币数；无法凑成返回 -1。

  • 例：coins = [1,2,5], amount = 11 → 3（5+5+1）。
  • 边界：amount = 0 → 0；coins = [2], amount = 3 → -1（今日本地测例）。

涉及算法 ​

标签一句话
完全背包 DP每种硬币可用无限次，求最小值
一维 DPdp[a] = 凑金额 a 的最少枚数

教程对照：21 · DP 入门 · 一维 精讲题即本题，与 279 完全平方数同框架。

评价我的解法 ​

注释写「手搓的」——和教程模板几乎一致，是今天独立度最高的一题。

我的代码（摘自 322-零钱兑换/index.js，不含测例）：

javascript
var coinChange = function (coins, amount) {
  const dp = Array.from({
    length: amount + 1,
  }).fill(Infinity);

  dp[0] = 0;

  for (let i = 0; i <= amount; i++) {
    for (const coin of coins) {
      if (i < coin) {
        continue;
      }
      dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};

对在哪

  1. 状态与初值：dp[0]=0、其余 Infinity，无法凑成时自然落到 -1，处理正确。
  2. 转移式：注释里的 dp[i]=Math.min(dp[i],dp[i-coin]+1) 写对了，代码也一致。
  3. 剪枝：i < coin 时 continue，避免无效访问。
  4. 本地测例：[2], 3 → -1，说明边界有测。

糙在哪

  1. 循环顺序：外层金额、内层硬币是标准「完全背包最少值」写法；若与 518「组合数」对比，要记清两种顺序差异——今天可先固化这一种。
  2. 性能：92 ms 偏慢，常因 Array.from + 双重循环常数；可改 new Array(amount + 1).fill(Infinity)，面试够用即可。
  3. 注释里的笔误：dp[i-coins[n]] 用了 n 未定义，只是注释问题，但默写时别带进代码。

小结：322 已能当完全背包最少值模板背诵；与 279 对照，应能口述「dp 含义 → 初值 → 双重循环转移」三连。

最佳题解 ​

与当前实现相同，仅收紧写法：

javascript
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (a >= c) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};
  • 时间 O(amount × |coins|)，空间 O(amount)。
  • 为何够用：每种硬币无限次 → 内层遍历硬币、外层递增金额；求 min 而非 max/count 时这套顺序最常用。

关联题目 ​

题为何相关
279. 完全平方数硬币换成 1²,2²,…（今日同练）
518. 零钱兑换 II同背包，求组合数而非最少枚数
139. 单词拆分另一套「dp[i] 能否达成」的背包味

一句话带走 ​

零钱兑换：dp[0]=0，对每个金额试每种硬币，dp[a]=min(dp[a], dp[a-c]+1)，仍为 Inf 则 -1。