滚动数组 · O(m+n)

省空间：滚动数组与 Hirschberg 分治

比对基因、diff 文件，第一步都是填一张编辑距离表。序列对齐 DP：一张表跑出四种算法里那张表整张留在内存： $m+1$ 行、 $n+1$ 列，本页预设对 ALGORITHM 与 ALTRUISTIC（9 字符对 10 字符）合 110 格。串一长，先见底的不是时间，而是空间：两条 ${10^5}$ 长的序列要一张 ${10^{10}}$ 格的表，寻常机器装不下，而同量级的运算次数还跑得动。本页分两步处理空间维度：滚动数组把存量压到两行，顺带把回溯路径弄丢；Hirschberg 分治在 $O(m+n)$ 空间里把路径找回来。

1 · 滚动数组与丢失的路径

编辑距离的递推只向上看一行： $Edit(i,j)$ 由 $Edit(i-1,j-1)$ 、 $Edit(i-1,j)$ 、 $Edit(i,j-1)$ 三个值决定，前两个在第 $i-1$ 行，第三个是本行已算好的部分。填第 $i$ 行时，第 $i-2$ 行以上的值再也不会被读到。滚动数组（sliding window）据此只保留两行：算完一行，覆盖最旧的那一行。预设对上峰值存量从 110 格降到 22 格（ ${2 \times 11}$ ），距离照样得 6；算量一格没省，仍是 110。

代价在回溯。距离到手时表只剩最后两行，而重建路径要从 $(m,n)$ 一路读回 $(0,0)$ ，沿途每一步都要查当年的格值来判断走向。对齐类应用真正要的往往是对齐本身（哪里替换、哪里插入删除），距离只是它的评分。表丢了，路径跟着丢。

图 1-1 · 滚动数组填编辑距离表的单步执行。存活的两行着绿，更早的行变灰表示已被覆盖，读数并列存活格数与已算格数。末帧是回溯的困境：最优路径要穿过的格子多数已不在内存，值以「?」标出。可切换字符串对，观察峰值存量始终是

(n+1) \times 2

格。

2 · 中线断点与分治重建

Hirschberg 在 1975 年给出的补救 [1] 基于一条几何观察：从 $(0,0)$ 到 $(m,n)$ 的任何一条最优路径，都要在中线行 $\lfloor m/2 \rfloor$ 上穿过某一列。记 $\mathrm{fwd}[q]$ 为上半个子问题的距离，即 $A$ 的前半对 $B$ 的前缀 $B[1..q]$ ；从上往下滚动到中线即得整行。再记 $\mathrm{bwd}[q]$ 为 $A$ 的后半对后缀 $B[q+1..n]$ 的距离；把两串同时反转、再滚动一遍即得。穿过第 $q$ 列的最优路径代价是两者之和，故

Edit(A, B) \;=\; \min_{0 \le q \le n} \big( \mathrm{fwd}[q] + \mathrm{bwd}[q] \big),

取到最小值的 $q$ 就是一个断点（breakpoint）：某条最优路径在中线上经过 $(\lfloor m/2 \rfloor, q)$ 。两遍滚动只花 $O(m+n)$ 空间，却比单算距离多拿到一样东西：路径与中线的交点。对上下两半各自递归，断点越积越多；行数减到 1 时子问题只剩两行，直接用小全表回溯兜底。所有断点与底部的小段路径拼起来，就是完整的最优路径。

时间账：每层递归滚动的格子数与矩形面积同阶，上下两个子矩形的面积合计是上一层的一半（ $\frac{m}{2} h + \frac{m}{2} (n-h) = \frac{mn}{2}$ ），逐层减半的几何级数收敛，总量仍是 $O(mn)$ 。空间账：任一时刻在场的只有常数条长度不超过 $n+1$ 的行，加上 $O(\log m)$ 层递归栈与长 $O(m+n)$ 的路径本身，合计 $O(m+n)$ 。

图 2-1 · Hirschberg 分治的逐事件回放。蓝色矩形是当前递归的子问题，中线上的数字是 fwd[q] + bwd[q]，取最小处即断点，下方面板并列两条得分行与其和；已确定的断点逐步连成路径。可改写两条字符串，观察递归结构随串长的变化，以及三种算法存量与算量的对照。

注 · 表述的出处。「正反两遍得分行」的讲法沿用 Erickson 附录 D，而他在页边注里自己说明这并不是 Hirschberg 原论文的表述——原文 [1] 处理的是最长公共子序列而非编辑距离，页边注还建议改用 Chowdhury–Ramachandran 的边界分治来替代。本页跟随书里的版本，它与 §1 滚动数组的衔接最直接。

3 · 实测账本

三种算法在预设对 ALGORITHM 与 ALTRUISTIC 上的实测计数如下。存量按数组的分配与释放逐笔记账，不是从公式推出来的：

算法	距离	峰值存量（格）	算量（格）	路径
全表回溯	6	110	110	完整
滚动数组	6	22	110	无
Hirschberg	6	33	312	完整

峰值 33 的构成能在引擎里对上：顶层递归中，上半的 $\mathrm{fwd}$ 行（11 格）已算完攥在手里，反向那一遍滚动内部又同时活着两行（22 格）， ${11 + 22 = 33}$ 。三条行同时在场的这个瞬间，就是全程的空间峰值。

算量一列有笔账值得算细。书中对总时间的归纳结论是 $T(m,n) \le 2\alpha mn$ ，字面读作「至多是一次填表的两倍」；引擎实测却是 312 格，约为全表 110 格的 2.8 倍。归纳并没有错，是 $\alpha$ 的口径窄：那套账只计递推的内部格子，每遍滚动的第 0 行第 0 列这些边界格、递归底部小全表的格子，全摊在 $mn$ 主项之外，串越短它们占比越大。「两倍」只在主项意义下成立，engines.test.ts 的空间账本一测据此把实测上界锁在 3 倍。

4 · 省时间的路线

本页动的全是空间：滚动数组的算量原封不动，Hirschberg 为了找回路径反而多算到 312 格。要把 $O(mn)$ 的时间本身降档，得从表格内部找结构。多数格子的值能直接推出、不必逐格算，是稀疏性：只算 match point的路线；最优决策的位置随行列单调移动、候选区间可以互相挤压，是 Knuth 单调性：最优 BST 的根不回头与行最小值：Monge 与 SMAWK逐级加强的路线，最后在落地：SMAWK 加速一维分段 DP接回一个可运行的应用。Erickson 顺带解释了教材习题偏爱「只求最优代价」的原因：Hirschberg 的分治外壳几乎适用于任何 DP，能在同样的时间与空间界里把最优结构本身重建出来，于是「求出结构」相对「求出代价」不再是本质更难的要求。

5 · 参考文献

Hirschberg, D. S. (1975). A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18(6), 341–343.
Erickson, J. (2019). Advanced dynamic programming. In Algorithms (Appendix D). http://algorithms.wtf