LCS → Myers → LIS → virtual DOM

从 LCS 到 virtual DOM：四种视角

把一个列表变成另一个，最少动几下？这条线从「最小 diff 是什么」一路走到「框架为什么不追求最小」。只许增删时，最优解落在 LCS 上，回溯即得编辑脚本；git diff 用的 Myers 把它看成编辑图最短路, $O(nd)$ 不填满整张表；元素只是换位时，用 LIS 把删+增压成「移动」（Vue3 / React 的关键一步）；最后落到 virtual DOM：真正的树编辑距离 $O(n^3)$ 太贵，框架用 $O(n)$ 启发式 + key 做工程妥协。每节都能改输入、单步看表 / 图 / 脚本实时变化。四节依次：从 LCS 到编辑脚本 → Myers 编辑图最短路 → 把删+增压成移动 (LIS) → virtual DOM 的妥协。

1 · 从 LCS 到编辑脚本：diff 的最小增删

concept · LCS → edit script

要把序列 a 变成 b、且只许插入 / 删除（不许「替换」），最省的做法是：把两者最长公共子序列 (LCS)原地留下，a 里多出来的全删、b 里多出来的全插。所以最小编辑脚本 = keep(LCS) + del + ins，而编辑距离 $D = n + m - 2\cdot |LCS|$ 。这节先单步填出 LCS 的 DP 表，再从右下角回溯出一串 keep / del / ins 操作。

和「编辑距离」哪里不同？ 经典 Levenshtein 允许替换（一步把 x 改成 y），而 diff（git / 列表渲染）通常不替换——改一个元素 = 删旧 + 插新。少了「替换」这条捷径，最优解就落在 LCS 上。两者同源，这里走的是 diff 这一支。

读法： 绿框路径就是回溯走过的格子——走对角线(↖)时遇到相等字符，记一次 keep；走上(↑)记 del、走左(←)记 ins。Myers 算法给出同一个最小 diff，但它不填整张表，而是直接在编辑图上找这条最短路。

2 · Myers 算法：在编辑图上找最短路

algorithm · Myers O(ND)

git diff 用的就是它。把 diff 画成一张 $(n+1)\times (m+1)$ 的编辑图：从左上 (0,0) 走到右下 (n,m),向右 = 删 a 的一个字符、向下 = 插 b 的一个字符（各算一步），而当 a[x]==b[y] 时能免费走一段对角线 (snake) = keep。最少编辑数 = 这张图上的最短路。Myers 不填整张表，而是按编辑步数 $d = 0,1,2\dots$ 一层层往外推波前，第一次够到右下角时，d 就是答案。复杂度 $O(nd)$ ——两个序列越像（d 越小）越快。

只追踪「每条对角线能走多远」： 对角线编号 $k = x - y$ 。数组 $V[k]$ 记当前在对角线 k 上能到达的最大 x。每加一步预算 d，就从邻居对角线 $k-1$ （向右 / 删）或 k+1（向下 / 插）里挑更远的那个延伸，再贪心吃掉对角线。

为什么 git 用它： 源码改动通常很小（d 小）, $O(nd)$ 几乎线性；而 LCS 那张满表恒为 $O(nm)$ 。两者给出同一个最小编辑距离——从 LCS 到编辑脚本那节已验证 $d = n+m-2\cdot LCS$ 。换一个场景：当元素只是换了位置时，可以把删+插压成「移动」，见把「删+增」压成「移动」。

3 · 重排列表：把「删+增」压成「移动」

technique · LIS / 移动压缩

列表只是换了顺序（同一批 key，位置变了）时，naive diff 会把挪了位的元素当成「删旧 + 插新」——可它们其实只需移动。做法：对每个新位置算出它在旧列表的下标，得到一个数组 newIndexToOldIndex；在它上面求最长递增子序列 (LIS)——LIS 上的元素相对顺序没变、可以原地不动，只把其余移到位即可。移动次数 = $n - |LIS|$ ，最少。这正是 Vue3 patchKeyedChildren 与 React reconciler 决定「谁要移动」的关键一步。

为什么是 LIS? 若一组元素在新列表里的旧下标是递增的，说明它们彼此相对顺序没变——让这批保持不动、把别人插到它们之间，代价最小。要不动的越多越好 → 求最长递增子序列。

试试 $ABCD \to DCBA$ : 完全倒序时 LIS 只有 1 个，其余全得移动——移动次数无法压缩。再试 $ABCDE \to ABXDE$ :LIS = ABDE 不动，只删 C、挂 X。移动越少，真实 DOM 操作越省。

4 · virtual DOM：为什么不追求「理论最小」

reality · virtual DOM

LCS、Myers、LIS 移动压缩都在求最优 diff。但 React / Vue 的 reconciliation 有意不这么做——真正的树编辑距离是 $O(n^3)$ ，页面有上千节点时无法承受。于是框架用一套 $O(n)$ 的启发式：其一，只同层比较（不跨层移动节点）；其二，type 不同就整棵重建，不去寻找子树如何移动；其三，列表靠 key 按身份配对。代价是偶尔多做几次 DOM 操作，换来「足够快且可预测」。本节实测有 key vs 无 key 的差距。本节的 key 配对识别移动依赖 LIS。

key 并非总是更优： 点上面的「完全替换」( $ABC \to XYZ$ )——无 key 反而更省：它把三个节点的骨架原地复用、只改文字（3 次）；有 key 因为新旧 key 毫无交集，只能全删 + 全建（6 次）。key 的价值在「元素身份稳定、只是改变了位置」时；拿数组下标当 key则等同于没有 key（在某些情况下更差，会把不同元素的状态错配到一起）。

4.1 · 框架到底做了哪些取舍

启发式	理论最优会怎样	框架的妥协
跨层移动	把整棵子树挪到新位置（省重建）	不做。换父节点 = 旧的删、新的建
type 变化	尽量复用内部结构	$<div>\to <span>$ 直接整棵重建
列表顺序	最小移动 (树编辑距离 O(n³))	key 配对 + LIS,O(n) 求「不动骨架」
没给 key	—	退化成按 index 比对，顺序变化代价大

核心：用线性时间换「足够好」的结果。LIS 移动压缩正是「列表顺序」这一格的引擎。

用到的基础算法： LCS / LIS 都是经典动态规划 (DP);Myers 的「按步数推波前」与最短路、分支限界同源（按代价分层的 BFS）。本系列与编辑距离 (Levenshtein)互为对照：编辑距离允许「替换」，list diff 只做增删。

5 · 它真实跑在哪里

版本控制:git diff / diff 工具用 Myers 算法生成最小编辑脚本(unified diff)。
前端框架:React reconciler、Vue3 patchKeyedChildren 的 keyed diff + LIS 求最小移动。
协同编辑 / OT·CRDT：文档同步先 diff 出变更再传输、合并。
其他:jsdiff / diff-match-patch 文本对比、数据库同步、rsync 增量、生物序列比对 (DNA)。