子问题视角：分治与动态规划

背包问题

标准形式

有 n 个物品，第 i 个重 weights[i]、值 values[i]。 背包容量 W，每个物品最多拿一次，问能装出的最大价值。

这是「前 i 个」模板的标准二维应用：

function knapsack01(W, weights, values) {
  const n = weights.length;
  // dp[i][w] = 只看前 i 个物品、容量为 w 时的最大价值
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      if (weights[i - 1] > w) {
        dp[i][w] = dp[i - 1][w];                  // 装不下，只能不拿
      } else {
        dp[i][w] = Math.max(
          dp[i - 1][w],                                        // 不拿
          dp[i - 1][w - weights[i - 1]] + values[i - 1],       // 拿
        );
      }
    }
  }

  return dp[n][W];
}

⭐ 二维版没有任何坑，闭着眼睛写就行。所有的坑都在压缩成一维之后。

压成一维：方向决定了拿几次

注意到 dp[i][*] 只依赖 dp[i-1][*]，那一整个二维数组是浪费的：

// 0-1 背包：容量倒序
function knapsack01_1d(W, weights, values) {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = W; w >= weights[i]; w--) {        // ← 倒序
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}
// 完全背包（每个物品可拿无限次）：容量正序
function knapsackComplete_1d(W, weights, values) {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = weights[i]; w <= W; w++) {        // ← 正序
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}

两个函数只有内层 for 的方向不同，解的却是两个不同的问题。

🚨 为什么方向能改变问题

关键在 dp[w - weights[i]] 这一格，在读它的那一刻，它是新值还是旧值：

  • 倒序（w 从大到小）：w - weights[i] 比 w 小，这一轮还没被更新过， 读到的是「上一行」的值，也就是「还没考虑这个物品」的状态。 → 这个物品最多被用一次 → 0-1 背包
  • 正序（w 从小到大）：w - weights[i] 比 w 小，这一轮已经更新过了， 读到的是「这一行」的值，可能已经包含了这个物品。 → 这个物品能被反复叠加 → 完全背包

⚠️ 写反了不报错、不越界，只是默默解了另一道题。而且是精确地解了另一道题：

0-1 背包写成正序   ≡  完全背包的正确答案     3000 组随机输入逐个相等
完全背包写成倒序   ≡  0-1 背包的正确答案     3000 组随机输入逐个相等

所以症状是严格单向的：

0-1 写成正序    与正确答案不同 80.4%，其中 100% 偏大（从不偏小）
完全写成倒序    与正确答案不同 80.4%，其中 100% 偏小（从不偏大）
碰巧相同        各 19.6%

⭐ 「偏大 / 偏小」这个方向可以当诊断用：0-1 背包的答案偏大， 八成是内层循环写成了正序，不用去查转移方程。

⭐ 记忆锚点：倒序 = 保守 = 只拿一次。 倒着走的时候左边还是旧数据， 借不到自己刚放进去的东西。

🚨 第二个方向：循环嵌套顺序决定组合还是排列

这条比上一条更隐蔽，因为它跟「拿几次」是完全独立的另一个维度。

以「凑出金额 amount 有几种方法」为例（完全背包计数）：

// 外层物品、内层容量 → 组合数（1+2 和 2+1 算同一种）
function combinationCount(coins, amount) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const c of coins) {
    for (let a = c; a <= amount; a++) dp[a] += dp[a - c];
  }
  return dp[amount];
}
// 外层容量、内层物品 → 排列数（1+2 和 2+1 算两种）
function permutationCount(coins, amount) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) if (a >= c) dp[a] += dp[a - c];
  }
  return dp[amount];
}

coins = [1,2,5], amount = 5：组合数是 4（1×5、1×3+2、1+2×2、5）， 排列数是 9。差得很远。

⚠️ 而求最大值 / 最小值的题里，这两种顺序结果完全相同 —— Math.max 和 Math.min 不在乎你以什么顺序把候选喂给它。实测：

求最大值（完全背包最大价值）   两种嵌套顺序 5000 组，结果不同 0 组
求最小值（零钱兑换最少硬币）   两种嵌套顺序 5000 组，结果不同 0 组
计数（凑出金额有几种）        两种嵌套顺序 5000 组，结果不同 51.6%

⭐ 最值题上一次都不会错，所以你可能在无数道题里随手写、一直没事， 直到遇上第一道计数题才被这个坑掉进去。

📌 计数题的最小反例小得可怜：coins = [1,2], amount = 3 —— 组合数 2（1+1+1、1+2），排列数 3（多了个 2+1）。

📌 判据：只要题目在数「有几种」，就必须想清楚它问的是组合还是排列。 问最值的时候，随便写。

两个维度，别混

这两条经常被搅在一起讲，其实是正交的：

你要控制的 靠什么
每个物品能拿几次 内层容量循环的方向（倒序 = 一次，正序 = 无限）
算组合还是排列 循环的嵌套顺序（物品在外 = 组合，容量在外 = 排列）

⭐ 想清楚这是两件事，就不会出现「为了改成排列数而把倒序改成正序」这种错位修改。

伪装成背包的几道题

分割等和子集 —— 能否把数组分成和相等的两半。 等价于「能否用这些数恰好凑出 sum/2」，就是 0-1 背包的可行性版本：

function canPartition(nums) {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2 !== 0) return false;             // 奇数直接否
  const target = sum / 2;

  const dp = new Array(target + 1).fill(false);
  dp[0] = true;                                 // 凑 0 永远可行：什么都不拿

  for (const x of nums) {
    for (let w = target; w >= x; w--) {         // 倒序：每个数只能用一次
      dp[w] = dp[w] || dp[w - x];
    }
  }

  return dp[target];
}

零钱兑换（最少硬币数）—— 完全背包求最小值：

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (const c of coins) {
    for (let a = c; a <= amount; a++) {         // 正序：硬币可以重复用
      dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

⚠️ 初值必须是 Infinity 而不是 0 或 -1。两种写法的症状都是常量，方向正好相反：

初值 0     dp[a] = min(0, …) 永远选中那个假的 0        →  答案恒为 0
初值 -1    dp[a] = min(-1, …) —— -1 比任何真实答案都小  →  答案恒为 -1

coins=[1,2,5], amount=8 时初值 -1 的整张 dp：
  [0, -1, -1, -1, -1, -1, -1, -1, -1]      ← 第 0 格之后一格都没被更新过

🚨 用 -1 的版本永远说「凑不出」（3000 组随机输入无一例外）， 所以它有 37.3% 的概率碰巧对 —— 正好是那些真的凑不出的用例。 用 0 的版本永远说「0 枚硬币」，只在 amount = 0 时碰巧对。

⭐ 两者共同的毛病不是「污染」，是初值本身就是最优的， 于是那一行 Math.min 从头到尾没起过作用。 👉 「不可达」必须用一个不可能赢过任何真实答案的值表示 —— 求最小用 Infinity，求最大用 -Infinity。

怎么认出一道题是背包

看到「从一堆东西里挑一些，在某个上限内，求最大/最小/有几种」，就往背包上套。 然后问三个问题：

  1. 每样能拿几次？→ 决定内层循环方向
  2. 求最值还是计数？→ 计数才需要管嵌套顺序
  3. 「容量」是什么？→ 有时候是重量，有时候是金额，有时候是目标和

下一步

背包的状态是「前 i 个 + 剩余容量」，仍然是一维推进。 接下来三篇换三种状态的形状： 区间 DP（状态是一段区间）、 树形 DP（状态是一个节点）、 状态机 DP（状态是当前身份）。

⭐ 顺带记一下：上面从二维压到一维的那一步， 就是状态压缩，本章最后一篇会专门讲 —— 包括什么时候不该压。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。