15.4　空间优化与滚动数组

学习目标：学完本节，你能

• 用"依赖宽度"这一个概念，判断一张 DP 表能不能压、能压到几维；
• 把"依赖上一行 + 本行左边"的问题压成一维（多用一个临时变量）；
• 说清内层遍历的方向由依赖关系决定 —— 并解释为什么背包要逆序、编辑距离要正序；
• 说出压缩带来的三项代价，以及"什么时候不该压"。

先修：15.3（背包的二维→一维压缩）、15.2（状态定义）。 固定术语：0/1 背包、状态转移方程、动态规划。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、直觉与实测：省下来的到底是什么

15.3 节做了一件事：把 0/1 背包的二维表压成了一维数组。但它只说了"因为只依赖上一行"，没有系统化。

这一节把那个判断变成一套可以套用的方法。

先看它到底省了多少（15.3 那节的规模还太小，看不出量级）：

  规模：200 件物品，容量 20,000

    实现                    结果          单次分配        耗时
    --------------------    ----------    ------------    --------
    二维 dp[i][c]               51,781    16,080,848 B      5.69 ms
    一维 dp[c]                  51,781        80,032 B      2.12 ms

  两者结果一致：True
  内存压缩比：200.9 倍

16 MB → 80 KB。 省下来的不是"一点零头"，而是 99.5%。

这个倍数从哪来？

    二维表有 201 行 × 20001 列 = 4,020,201 个格子；
    一维数组只有 20,001 个格子。
    比值 ≈ 行数 = 201

压缩比 ≈ 行数 —— 二维表里那 $n$ 行，我们其实只需要其中一行。

而且容量越大、物品越多，这个倍数越大 —— 这是量级上的节省，不是常数优化。

那么问题来了：是不是所有 DP 表都能这么压？

二、形式化：依赖宽度

能不能压，只取决于一件事：

算 dp[i][...] 的时候，它需要回头看多少东西？

把这个"回头看的范围"叫做依赖宽度：

判断方法只有一句话：

把转移方程右边所有的"来源"列出来，看它们分布在哪些行上。

只涉及上一行的 → 一维就够；涉及本行的 → 还要注意方向；涉及全部历史的 → 别压了。

滚动数组是这套思路的一般形式：

如果需要 $k$ 行，就用 dp[i % k][...] 循环使用这 $k$ 行 —— 第 $i$ 行覆盖掉第 $i-k$ 行（它的数据已经用不着了）。

$k = 1$ 时就是"一维数组"，$k = 2$ 时就是"滚动两行"。

下一节用一个"依赖上一行 + 本行左边"的例子，把这个判断走一遍。

三、编辑距离：一个"依赖上一行 + 本行左边"的例子

问题：把字符串 A 改成字符串 B，每次可以插入/删除/替换一个字符，求最少操作次数。

状态：$dp[i][j]$ = 把 A 的前 $i$ 个字符改成 B 的前 $j$ 个字符，最少要几步。

转移方程（枚举最后一步的三种操作）：

    dp[i][j] = min( dp[i-1][j]   + 1,      删除（A 多了一个字符）
                    dp[i][j-1]   + 1,      插入（B 多了一个字符）
                    dp[i-1][j-1] + cost )  替换或匹配（cost 是 0 或 1）

先看依赖宽度

把三个来源标在表格上（当前格子是 $[i][j]$）：

结论：只依赖上一行和本行左边 —— 属于"压成一维"那一档。

但"本行左边"这一项，会带来两个后果：

1. 本行必须【从左往右】算（算 $dp[j]$ 时 $dp[j-1]$ 必须先算好）
2. 需要一个临时变量存住左上角的值

为什么需要临时变量？

这是压缩时最容易漏的一步：

一维数组 dp[j] 在算之前，装的是"上一行的 $dp[i-1][j]$"。

一旦算出本行的 $dp[j]$ 并写回去，那个"上一行的值"就没了。

而下一轮 $j+1$ 需要 $dp[i-1][j]$（也就是现在这个 $j$ 位置的旧值）作为它的左上角。

所以必须【覆盖前先存下来】。

代码：

var dp = new int[m + 1];
for (int j = 0; j <= m; j++) dp[j] = j;      // 第 0 行

for (int i = 1; i <= n; i++)
{
    int prevDiag = dp[0];                    // ★ 保存 dp[i-1][j-1]
    dp[0] = i;                               // dp[i][0] = i
    for (int j = 1; j <= m; j++)             // ★ 本行【从左往右】
    {
        int prevUp = dp[j];                  // 覆盖前先存下 dp[i-1][j]
        int cost = a[i - 1] == b[j - 1] ? 0 : 1;
        dp[j] = Math.Min(
            Math.Min(dp[j] + 1, dp[j - 1] + 1),   // 上、左（左已是本行的值）
            prevDiag + cost);                     // 左上（用临时变量）
        prevDiag = prevUp;                   // 为下一个 j 准备左上角
    }
}

两个变量各司其职：

实测

  样例："kitten" -> "sitting"
    二维解法：3
    一维解法：3
    （正确答案是 3：kitten -> sitten -> sittin -> sitting）

  2000 组随机字符串：两种解法结果不一致的组数 = 0

内存对比（两个长度 2,000 的字符串）：

    实现                    结果        单次分配
    --------------------    --------    ------------
    二维 dp[i][j]              1,040    16,016,048 B
    一维 dp[j]                 1,040         8,032 B

  内存压缩比：1994.0 倍

1994 倍 —— 因为这里的"行数"是 $n = 2000$，压缩比自然也是这个量级。

四、方向问题又来了（但这次结论相反）

15.3 节花了很大篇幅讲"背包必须逆序"。现在编辑距离的一维写法，用的是【正序】。

两个问题看起来都在"同一行里左右移动"，为什么方向相反？

答案在"你要的是哪一轮的值"：

两者都"依赖同一行"，但一个要的是【旧的】，一个要的是【新的】—— 方向自然相反。

所以"逆序/正序"根本不是一条要背的口诀，而是"你需要哪一轮的值"的直接推论。

一个统一的判断方法：

写下转移方程后，对每一个来源问一句：

"在当前这一轮里，这个位置【有没有可能已经被覆盖过】？"

• 可能被覆盖，而我要旧的 → 必须逆序（或提前存下来）
• 必须已经被覆盖，我要新的 → 必须正序
• 不会互相干扰 → 方向随便

15.3 节那个"背包写错正序就只有 3.4% 正确"的实验，就是第一行判断失败的样子。

五、压不动的第三种情况

前面两种都能压。第三种不能。

  回顾 15.2 节的 LIS 转移方程：
    dp[i] = max( dp[j] ) + 1     （对所有 j < i 且 a[j] < a[i]）

  n = 3,000 时，dp 数组必须完整保留：单次分配 12,024 B
    （3,000 个 int = 12,000 B，一个不多一个不少）

注意那个 max 的范围是【所有 $j < i$】 —— 不是"上一行"，也不是"左邻"，而是【从头到现在的全部历史】。

所以整张表一个格子都不能丢。

为什么不能像背包那样"只留一行"？

因为算 $dp[i]$ 时，前面每一个 $dp[j]$ 都【有可能】被用到 —— 你无法提前知道哪个 $j$ 的 $a_j$ 会比 $a_i$ 小。

背包不一样：它依赖的范围是"容量更小的那些" —— 而这个范围是【确定的】（c - w 以前），所以可以只留一行、靠方向控制顺序。

三个档位总结：

六、压缩的代价

省下 99.5% 的内存，代价是什么？

所以有一条务实的工程建议：

先用二维把问题写对、跑通、对拍过，再考虑压缩。

理由很简单：二维写法容易验证（能打印、能对拍），一维写法只能靠结果对不对来判断 —— 而"结果不对"这个信号，在 DP 里往往来得太晚。

什么时候【不该】压？

七、练习

练习 15.4.1（判断依赖宽度） 对下面的 DP，判断能不能压成一维，如果能，说明要不要临时变量、方向如何：

(a) 爬楼梯：f(n) = f(n-1) + f(n-2) (b) 数字三角形：f(r, c) = max(f(r-1, c-1), f(r-1, c)) + a[r][c] (c) LIS 的 $O(n^2)$ 解法：dp[i] = max(dp[j]) + 1（$j < i$） (d) 编辑距离：dp[i][j] 依赖 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]

练习 15.4.2（手工压缩） 数字三角形（练习 15.4.1(b)）是可以压成一维的。

(a) 它的依赖宽度是多少？ (b) 压成一维后，内层循环的方向该怎么走？为什么？ (c) 需要临时变量吗？

练习 15.4.3（判断） 判断对错并说明理由： (a) 所有二维 DP 都能压成一维。 (b) 一维写法一定比二维写法快。 (c) 一维写法的内层循环必须逆序。 (d) 压成一维后，如果方向写错了，程序会报错。

练习 15.4.4（挑战·滚动数组的一般形式） 一个 DP 的状态依赖前两行（比如 dp[i][j] 依赖 dp[i-1][j] 和 dp[i-2][j]）。

(a) 能不能压成一维？为什么？ (b) 用"滚动数组"的话，需要几行？ (c) 写出用 % k 取模定位行号的代码框架。

八、练习答案

15.4.1

15.4.2

(a) 依赖宽度 = 1（只依赖上一行）。

具体来说是上一行的两个位置：$[r-1][c-1]$（左上）和 $[r-1][c]$（正上）。

(b) 内层 $c$ 应该【从左往右】还是【从右往左】？——要看具体写法。

先看转移：

$$f(r, c) = \max\big(f(r-1, c-1),\ f(r-1, c)\big) + a_{r,c}$$

压成一维后，dp[c] 在算之前装的是【上一行的 $f(r-1, c)$】。

算 dp[c] 需要：

• $f(r-1, c)$ —— 就是 dp[c] 自己（覆盖前的值） ✓
• $f(r-1, c-1)$ —— 是 dp[c-1]（覆盖前的值）

关键：如果从左往右算，那么算 dp[c] 时 dp[c-1] 已经被本行覆盖了 —— 拿到的就不是 $f(r-1, c-1)$ 了 ✗

所以必须【从右往左】算：

for (int c = cols - 1; c >= 0; c--)        // ★ 从右往左
    dp[c] = Math.Max(dp[c], dp[c - 1]) + a[r][c];

从右往左时，dp[c-1] 还没被本行碰过 —— 正好是 $f(r-1, c-1)$ ✓

(c) 不需要临时变量。

因为两个依赖源都在"上一行"，而且【从右往左】的遍历顺序天然保证了"读到的都还是旧值"。

注意这一点和编辑距离的对比：

	依赖	方向	临时变量
数字三角形	上一行的左邻和正上	从右往左	不需要
编辑距离	上一行 + 本行的左邻	从左往右	需要

差别就在于"有没有一项依赖本行"：一旦依赖本行左边，就必须正序（那行会被覆盖），于是左上角就得自己存。

15.4.3

(d) 是本节最该记住的一条： 压缩之后的 bug 是【静默】的 —— 这和 14.1 节贪心的错误是同一类现象。

也正因为如此，第六节那条建议才重要：先用二维写对、对拍过，再压。

15.4.4

(a) 不能压成一维，但能压成"两行"。

为什么不能压成一维？

因为算 dp[i][j] 需要 $dp[i-2][j]$ —— 而一维数组只有一个位置存 $j$，算到第 $i$ 行时，第 $i-2$ 行的数据早就被第 $i-1$ 行覆盖了。

一维数组的容量不够装"两行"。

(b) 需要 2 行。

(c) 代码框架

// rows[0]、rows[1] 交替使用
var dp = new int[2][];
dp[0] = new int[m + 1];
dp[1] = new int[m + 1];

for (int i = 0; i < n; i++)
{
    int cur = i % 2;            // ★ 本行放哪
    int prev = (i - 1 + 2) % 2; // ★ 上一行
    int prev2 = (i - 2 + 2) % 2;// ★ 上两行

    for (int j = 0; j <= m; j++)
    {
        // 注意：i < 2 时 prev / prev2 还不存在，要单独处理边界（或用哨兵行）
        dp[cur][j] = Combine(dp[prev][j], dp[prev2][j], ...);
    }
}
// 答案在 dp[(n - 1) % 2][m]

⚠️ 两个坑：

1. i % 2 在前两行时会绕回去（$i = 0$ 时 prev = 1，但第 1 行还没算过）—— 要么单独处理前两行，要么多开一行当哨兵。
2. 答案的位置变成了 dp[(n-1) % 2][m]，不再是"最后一行" —— 这个细节改完容易忘，而且忘了不会报错，只会读到一行旧数据。

这两条都印证了第六节那句话：压缩会引入"不报错的错误"，所以先写对再压。

九、常见错误

十、本节总结

1. 能不能压，只看一件事：依赖宽度 —— 算 dp[i][...] 时需要回头看多少东西。
2. 实测一：0/1 背包二维 16 MB → 一维 80 KB，压缩 200.9 倍； 比值 ≈ 行数（$n$），容量和物品越多，省得越多。
3. 三个档位：
   • 依赖上一行 → 一维（背包、数字三角形）
   • 依赖上一行 + 本行左边 → 一维 + 临时变量（编辑距离）
   • 依赖全部历史 → 压不了（LIS 的 $O(n^2)$）
4. 实测二：编辑距离二维 16 MB → 一维 8 KB，压缩 1994 倍； 2000 组随机字符串对拍零不一致。
5. 方向问题（15.3 的延伸）："逆序还是正序"由"你要的是哪一轮的值"决定 —— 背包要旧值所以逆序，编辑距离要新值所以正序。这不是口诀，是推论。
6. 滚动的本质：需要 $k$ 行就用 dp[i % k] 循环使用；$k=1$ 是一维，$k=2$ 是滚动两行。
7. 压缩的代价：可读性、调试难度、方向陷阱、不可逆。 工程建议：先用二维写对并跑通，再压缩。
8. 压缩后的 bug 是静默的（3.4% 正确率却"正常运行"）—— 和 14.1 节贪心的错误同一类。

本章小结：第 15 章把动态规划讲完了。

贯穿本章的三条线索：

1. 「DP 的两个前提」（14.1 提出，本章落地）： 最优子结构决定"能不能用 DP"，重叠子问题决定"用 DP 划不划算"。

2. 「状态定义是 DP 里最值钱的一步」： 15.2 用"差一个词"证明了它（37.4% vs 100%）， 15.3 用 LIS 证明了它（同一个问题，换状态定义，复杂度从 $O(n^2)$ 到 $O(n\log n)$）。

3. 「实现细节不是细节」： 遍历方向（15.3）、依赖宽度（15.4）、临时变量（15.4）—— 这些看起来琐碎的细节，每一个写错都会静默给出错误答案。

下一章衔接：到这一章为止，本书把数据结构（1–12 章）和算法设计范式（13–15 章）都讲完了。

第 16 章是收束：

• 16.1 选型手册 —— 把散落在全书各处的对比表汇总成一张"按场景查"的表
• 16.2 性能剖析 —— 呼应 1.1 节埋的"缓存与 GC 导致实测偏差"，讲怎么在真实项目里定位性能问题
• 16.3 综合项目 —— 一个任务调度器，会同时用上拓扑排序（13.1）+ 优先队列（11.4）+ 哈希表（第 6 章）

换句话说：从下一章开始，不再有新的算法 —— 只有"怎么把已经学过的这些挑出来、用对、并且验证它真的对"。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "15.4",
  "title": "空间优化与滚动数组",
  "covered": [
    "依赖宽度这一个概念作为压缩判据",
    "实测一：0/1 背包二维 16MB vs 一维 80KB（压缩 200.9 倍），比值≈行数",
    "编辑距离的转移方程与三个依赖来源（上/左上/左）",
    "依赖上一行+本行左边时的压缩方法（两个临时变量 prevDiag / prevUp）",
    "实测二：编辑距离压缩 1994 倍、2000 组对拍零不一致",
    "「方向由依赖决定」的统一判断方法（要旧值→逆序，要新值→正序）",
    "背包逆序与编辑距离正序的对照分析",
    "依赖全部历史时压不了（LIS，实测 dp 数组必须完整保留）",
    "滚动数组的一般形式（dp[i % k]，k=1 即一维）与它的两个坑",
    "压缩的四项代价与「先写对再压」的工程建议",
    "第 15 章全章小结与三条主线"
  ],
  "unresolved": [
    "滚动数组在 k>=2 时的边界处理只给了框架（练习 15.4.4），未给完整实现",
    "输出路径而非仅答案时的空间优化未展开",
    "第 16 章的选型与综合留到下一章"
  ],
  "canonical_terms": {
    "依赖宽度（Dependency Width）": "算 dp[i][...] 时需要回看多少行；决定能否压缩以及压到几维",
    "滚动数组（Rolling Array）": "需要 k 行时用 dp[i % k] 循环使用这 k 行，第 i 行覆盖第 i-k 行",
    "0/1 背包（0/1 Knapsack）": "一维写法需逆序遍历（要的是上一轮的值）"
  },
  "symbols_units": {
    "dp[i][j]": "二维状态",
    "k": "滚动数组保留的行数",
    "prevDiag / prevUp": "编辑距离压缩时保存的 dp[i-1][j-1] 与 dp[i-1][j]"
  },
  "assumptions": [
    "读者已掌握 15.3 的背包二维→一维压缩",
    "读者理解 12.1 节「不要用 GC.GetTotalMemory 差值法测内存」的教训",
    "本节内存一律用 GC.GetAllocatedBytesForCurrentThread() 测量"
  ],
  "word_count_actual": 2740,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch15/Sec154/",
    "实验一：背包 200 件物品/容量 20000 时，二维 16,080,848 B vs 一维 80,032 B（200.9 倍），耗时 5.69 / 2.12 ms，为实测",
    "实验二：编辑距离 kitten->sitting 两种解法均为 3；2000 组随机字符串零不一致；长度 2000 时二维 16,016,048 B vs 一维 8,032 B（1994 倍），为实测",
    "实验三：LIS n=3000 时单次分配 12,024 B（3000 个 int），为实测",
    "内存一律用 GC.GetAllocatedBytesForCurrentThread() 测量，未使用 GC.GetTotalMemory 差值法",
    "术语写法与 glossary.md 一致（0/1 背包、状态转移方程、动态规划）"
  ],
  "known_issues": [
    "实验一初版规模取 200 件物品 + 容量 20000，二维表分配 16 MB —— 这个规模是试出来的：再大（如 500×50000 会到 100 MB）会让 GC 压力过大影响计时，再小则压缩倍数不直观",
    "编辑距离的一维写法里需要两个临时变量（prevDiag 存 dp[i-1][j-1]、prevUp 存 dp[i-1][j]），初版只用一个导致结果错误 —— 正文改为把两个变量的职责列成表格讲清楚，避免读者自己推",
    "初版想用「打家劫舍」作为「依赖两行」的例子，但它其实能压到 O(1)（15.2 已讲过一维状态就够），不适合当滚动两行的示例 —— 改为在练习 15.4.4 里用抽象例子讲滚动框架"
  ],
  "next": "16.1 选型手册：按场景选数据结构"
}