unified engine · 2×2 象限

序列对齐 DP：一张表跑出四种算法

LCS（最长公共子序列）、编辑距离(Levenshtein)、Needleman–Wunsch（全局序列比对） 看着是三道题，底层却是同一个二维 DP。它们都在一张「行 = 序列 A、列 = 序列 B」的表上填格：每个格子 $F[i][j]$ 只从对角（替换 / 匹配）、上（删）、左（插）三个来源里，按 max 或 min 取最优。真正区分这几个算法的，只是每个方向记什么代价、以及取 max 还是 min 这一组参数——本页把它抽象成一个 spec，用同一个引擎让你当场切换，看同一张表如何变成不同算法。

1 · 一个递推式，三个来源

把 A 排成行、B 排成列， $F[i][j]$ 表示「A 的前 i 个字符」与「B 的前 j 个字符」之间的最优值。要算它，只需看三个已经算好的邻居，各加上一步操作的代价，再聚合：

F[i][j] = agg {  ↖ F[i−1][j−1] + d(a, b)      对角:a 与 b 对位(相等=匹配,不等=替换)
                 ↑ F[i−1][j]   + up(a)         上:删去 A 的字符 a
                 ← F[i][j−1]   + left(b)  }     左:插入 B 的字符 b

其中 agg 是 max 或 min; d / up / left 是三个方向各自的代价函数。边界（第一行 / 第一列）对应「一方为空串」，沿单一方向累积即可。填完整张表后，从终点 $F[m][n]$ 沿方向指针回溯，就能还原出完整的对齐与编辑脚本。下面这张表里，角标 $↖ ↑ \leftarrow$ 标的就是每格的最优来源方向。

2 · 同一个引擎，切 spec 换算法

把四个算法按两个维度摆成一张 2×2 矩阵：纵轴是聚合方向—— $\max \cdot 相似$ （分越高越像）对 $\min \cdot 代价$ （代价越低越像）;横轴是代价取法——朴素(0 / 1)对 带权 / 打分。四个格子恰好落到四个算法：

LCS（max · 朴素）：相等才 +1，删插不计——求最长公共子序列。
Needleman–Wunsch（max · 打分）：匹配 / 失配 / gap 各给一个可正可负的得分，求总分最高的全局比对。
编辑距离（min · 朴素）：增 / 删 / 改各记 1，求把 A 改成 B 的最少操作数。
带权编辑（min · 带权）：增 / 删 / 改各带不同权重，求最小总代价。

点矩阵切换算法；改 A / B 或点预设换输入；用「下一步 / 播放」逐帧看填表与回溯，代码面板会高亮当前执行行。Needleman–Wunsch 与带权编辑还会出现参数滑块，以及一个翻转视角按钮（见下文「同构」）。

3 · 四种 spec 并排看

四个算法的差别，全部浓缩在下面这张表里——同一套 solve(A, B, spec) 填表逻辑，只是喂进去的 d / up / left / agg 不同：

算法	对角 d(a, b)	上 up(a)	左 left(b)	agg
LCS	`a==b ? 1 : −∞`	`0`	`0`	`max`
Needleman–Wunsch	`a==b ? match : mismatch`	`gap`	`gap`	`max`
编辑距离	`a==b ? 0 : 1`	`1`	`1`	`min`
带权编辑	`a==b ? 0 : Wsub`	`Wdel`	`Wins`	`min`

LCS 为什么对角是 $-\infty$ ? LCS 不允许「替换」这一步：两个字符不相等时，绝不能走对角占一个匹配位，只能从上或左绕过（即删或插）。把失配的对角代价设成 $-\infty$ ，在 max 聚合下它永远不会被选中，自然就禁掉了替换。编辑距离则相反——替换是合法的一步，失配对角记 1。

4 · 同构：相似度与代价是同一枚硬币

为什么有的算法求 max、有的求 min？因为相似度 = −代价。把一个 spec 的全部代价取负、并把 max 翻成 min（反之亦然），得到的是同一个问题的另一种说法：最优路径完全不变，只是表里每个数字镜像取负。交互台里 Needleman–Wunsch / 带权编辑下的翻转视角按钮，演示的正是这个变换——把「打分越高越好(max)」翻成「代价越低越好(min)」，回溯出的对齐一模一样。

这解释了为什么生物信息学惯用 Needleman–Wunsch 的得分(max)语言，而编辑距离用代价(min)语言——两者并非不同算法，只是同一个 DP 在符号上的两种约定。理解这一点，四个格子就真正合成了一个。

5 · LCS 与编辑距离的化归

当编辑距离只允许增、删，不允许替换时，它与 LCS 之间有一个精确等式：

仅增删的编辑距离 = m + n − 2 · LCS(A, B)

直觉是：两串各长 m / n，公共子序列里的 LCS 个字符两边都保留，其余 $(m - LCS)$ 个要删、 $(n - LCS)$ 个要插，合计 $m + n - 2\cdot LCS$ 。在交互台切到 LCS 模式时，读数区会实时算出这个化归值，可与切到编辑距离时的结果对照——注意编辑距离额外允许替换，所以它通常更小或相等。

6 · 近亲：DTW——当序列是数值、要对齐的是时间轴

前面四个算法比的是字符序列。把序列换成数值（音频帧、笔迹坐标、传感器采样），问题就从「怎么改」变成「两条随时间变化、但快慢不同的信号，怎么对齐、有多像」——这就是 DTW（Dynamic Time Warping，动态时间规整）。它和编辑距离是近亲：同样是一张二维表、同样三方向、同样取 min。但有三处关键不同，别把它当成第五个 spec 强行并入上面的引擎：

格子代价是距离：每格付 $dist(a, b) = |a - b|$ （实数），不是 0 / 1 或操作权重。
三方向付同一份代价: $D[i][j] = dist(a, b) + \min (↖, ↑, \leftarrow )$ ——三个前驱都加同一个 dist 再取最优；编辑距离则是三方向各付各的（对角 d、上 up、左 left）。
边界是 ∞、产物是 warping 路径: $D[i][0] = D[0][j] = \infty$ 逼对齐从 (1,1) 起；回溯得到的是「一个点对多个点」的时间轴伸缩关系，不是增删改的编辑脚本。

下面的 lab 用两条数值序列演示：柱高是信号幅度，回溯连线是对齐关系。选**「同峰·不同速」预设，能看到两条形状相同、快慢不同的信号，峰值被拉伸对齐**到一起（一个点连到对面多个点）。

这就是字幕对齐 (forced alignment) 的内核。 已知一段音频 + 对应文本，把音频特征帧序列与文本音素序列用 DTW / HMM 对齐，就能算出「第几个字落在哪个时间区间」，生成逐字高亮的卡拉 OK 字幕。手势识别同理：把用户画的轨迹与模板轨迹对齐，快慢、点数不同也不影响判定。这类功能在前端通常藏在媒体 / 手势库内部，你调用而非自己写。