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

状态压缩

能压的条件只有一条

dp[i][*] 只依赖 dp[i-1][*]，不依赖 dp[i-2][*] 或更早。

满足这一条，那 n 行里同时有用的永远只有相邻两行，其余全是死重量，可以砍掉。

背包满足（只看上一行）， 编辑距离也满足。 不满足的例子：某些需要回看两行的递推（比如「不能连续选相邻两个」的变体）， 那种只能压到两行，压不到一行。

方向怎么定：看依赖的列在左边还是右边

砍掉第一维之后，dp[j] 这一格在被写入之前，存的是上一行的值； 被写入之后，变成这一行的值。所以问题变成： 你要读的那一格，此刻应该是新的还是旧的？

dp[i][j] 依赖 需要的是 遍历方向
dp[i-1][j']，且 j' < j 旧值 倒序（从大到小）
dp[i][j']，且 j' < j 新值 正序（从小到大）

⭐ 一句话：要旧值就倒着走，要新值就正着走。

0-1 背包依赖 dp[i-1][w-weight]（上一行、左边），要旧值 → 倒序。 完全背包故意要读到本行的新值（这样物品能重复拿）→ 正序。 这两条在背包那篇讲过，这里是它的一般形式。

⭐ 方向写反的后果有个漂亮的刻画：0-1 背包写成正序，答案恰好等于完全背包。 2000 组随机输入上逐个相等，一次例外都没有。

0-1 背包压一维，写成正序（3000 组随机输入）
  与二维版不同   2280 组 = 76.0%
  其中偏大       2280 组 = 100%     ← 从不偏小

👉 所以「方向写反」不是算乱了，是悄悄换了一道题 —— 每件物品被允许拿无限次。答案只会偏大，而且偏得「看起来很合理」。

⚠️ 压缩是最后一步，不是第一步

先把二维版写对、跑通、测过，再压。

顺序反过来的代价是不对称的：一旦结果不对，你分不清是 状态转移的逻辑错了还是压缩的方向错了 —— 而这两种错的修法完全不同。 二维版写对之后，压缩只是一次机械变换，出错也只可能出在方向上， 排查范围一下子小了一半。

📌 更实际的一点：面试时二维版就够了。 除非面试官明确问「空间还能优化吗」， 否则先写清楚的版本，然后主动说一句「这里可以压到一维，因为只依赖上一行」—— 这比一上来就写个看不懂的一维版加分得多。

滚动数组：更安全的中间选择

如果懒得推方向，或者依赖关系复杂到不好判断，可以只压到两行：

function minDistanceRolling(s1, s2) {
  const m = s1.length, n = s2.length;

  let prev = new Array(n + 1);
  let curr = new Array(n + 1);
  for (let j = 0; j <= n; j++) prev[j] = j;      // 第 0 行

  for (let i = 1; i <= m; i++) {
    curr[0] = i;                                  // 每行的第 0 列
    for (let j = 1; j <= n; j++) {
      curr[j] = s1[i - 1] === s2[j - 1]
        ? prev[j - 1]
        : 1 + Math.min(prev[j - 1], prev[j], curr[j - 1]);
    }
    [prev, curr] = [curr, prev];                  // 轮换
  }

  return prev[n];                                 // 🚨 轮换过了，答案在 prev
}

⭐ 滚动数组的好处是不用推方向：prev 明确是上一行、curr 明确是这一行， 读哪个一目了然，正序倒序都行。空间从 O(mn) 降到 O(n)， 只比真正的一维版多一个数组。

🚨 唯一的坑是最后那一行 return prev[n]。因为循环末尾做了轮换， 最后一次计算的结果在 prev 里而不是 curr 里。 写成 return curr[n] 会返回倒数第二行的值（3000 组随机输入里答错 70.2%）。

⚠️ 但别指望「单字符样例测不出来」 —— 恰恰相反，m = 1 时它很容易暴露：

("a","a")     正确 0   写成 curr[n] → 1    🚨
("a","ab")    正确 1   写成 curr[n] → 2    🚨
("a","b")     正确 1   写成 curr[n] → 1    相同
("a","bc")    正确 2   写成 curr[n] → 2    相同

m=1 的 5000 组随机输入：只有 23.0% 碰巧相同

m = 1 时 curr[n] 恒等于第 0 行的值，也就是 s2.length。所以它碰巧对， 当且仅当 s2 非空、且 s1 那个字符压根不在 s2 里。 ⭐ 反过来就是最省事的自测：让那个字符出现在 s2 里，("a","a") 就够 —— 正确答案 0，写错立刻给 1。

⚠️ curr[0] = i 也不能漏。但它的症状不是「陈旧值污染」，是 NaN：

5000 组随机输入
  得到 NaN     3745 组 = 74.9%
  错的数字      262 组 =  5.2%
  碰巧算对      993 组 = 19.9%

🚨 第一轮的 curr 是全新的 new Array(n + 1)，curr[0] 是 undefined， 而 Math.min(…, undefined) 是 NaN，接着 1 + NaN 还是 NaN，一路传到底。 「curr 里残留着两行之前的数据」要到 i ≥ 3 才谈得上， 但 NaN 从第一轮就产生了。 ⭐ 好消息是这个错法比上一个吵得多：七成五直接给 NaN，一眼就知道出事了。

什么时候不该压

要还原具体方案的时候。

dp[m][n] 只告诉你「编辑距离是 3」。想知道具体哪三步， 得从 dp[m][n] 倒着回溯：看它是从 dp[i-1][j-1] 还是 dp[i-1][j] 转移来的， 一路走回起点。

🚨 压缩之后中间行全被覆盖了，这条路走不通。 类似地：

  • 输出最长公共子序列的内容（不只是长度）→ 不能压
  • 输出背包装了哪几个物品 → 不能压
  • 需要打印 dp 表来调试 → 不能压

⚠️ 这是个真实的取舍，不是「压了更好」。题目只要一个数字就压， 要方案就老老实实留着二维表。

📌 还有一种情况不值得压：n 本来就很小。 dp 是 100 × 100 的时候，一万个数字连 100 KB 都不到：

理论   10000 个 double × 8 字节            = 78 KB
实测   20 张 100×100 嵌套数组，平均每张占    83 KB 堆内存

⭐ 连 JS 的对象开销算进去也只有八十几 KB。压缩省下的内存毫无意义， 换来的是可读性下降和一个方向写反的风险。

位压缩：另一个叫「状态压缩」的东西

⚠️ 「状态压缩 DP」这个词还有另一个完全不同的含义，别搞混了：

用一个整数的二进制位表示一个集合（第 k 位是 1 表示元素 k 在集合里）， 把「所有子集」当成 dp 的状态。典型是旅行商问题（TSP）： dp[mask][i] 表示「走过 mask 这些城市、当前在 i」的最小代价。

它跟本篇讲的降维毫无关系 —— 那个是省空间，这个是用整数编码集合。

📌 面试里位压缩 DP 出现频率很低（状态数是 2ⁿ，n 稍大就不可行）。 「稍大」是多大，实跑一遍 TSP：

n      状态格子数 (2ⁿ·n)     转移次数      耗时
10             10,240         9,225        1 ms
14            229,376       319,501        6 ms
18          4,718,592     8,912,913      155 ms
20         20,971,520    44,826,643      640 ms
25        838,860,800            —          不用试了

⭐ n = 20 是实际的天花板（半秒多），再加 5 个城市格子数就涨 40 倍。 👉 所以题面给的 n 只要超过 20 出头，就可以直接排除位压缩这条路。

听到「状态压缩」先确认对方说的是哪个意思。

本章小结

子问题视角这一章到这里就完了：

  • 分治 —— 子问题不重叠，不用记
  • 动规框架 —— 重叠了，暴力递归 → 备忘录 → 递推
  • 子序列 —— 两套状态定义模板，先选模板再推方程
  • 背包 —— 遍历方向管次数，嵌套顺序管组合还是排列
  • 区间 DP —— 状态是一段区间，枚举分割点；顺序写错会静默偏小
  • 树形 DP —— 状态在节点上，返回值和答案往往不是一个东西
  • 状态机 DP —— 状态是当前身份，股票六道题是同一道
  • 状态压缩 —— 最后一步的空间优化，代价是丢掉方案还原能力

练习

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

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