最长公共子序列：相等斜取一格，不等取更大的一边
dp[i][j] 是 A 前 i 个与 B 前 j 个的 LCS。末尾相同就左上加一；不同就在「丢掉 A 尾」和「丢掉 B 尾」里取长的。
空前缀全是 0。A[i−1]==B[j−1] 时 dp[i][j]=dp[i−1][j−1]+1，否则 max(dp[i−1][j], dp[i][j−1])。答案在 dp[m][n]。时间 O(m·n)，空间 O(m·n)，可压成两行。
这是 LeetCode 1143. Longest Common Subsequence。给两个字符串 text1、text2，求最长公共子序列的长度。子序列可以跳着取，但不能打乱相对顺序。不要求连续，那是最长公共子串。
主例 text1 = "abcde"，text2 = "ace"。公共子序列 ace 长度 3，也是最长。演示场景给出填完的表，右下角 (5,3) 就是 3。
第一直觉是双指针扫：相同就两个都前进并计数，不同就只动一个。主例碰巧能对，但 "abc" 和 "acb" 会因先吃谁而吃亏。缺的是「两个前缀的最优长度」这张可以回头取的表。下面从这块缺口推出二维 DP。
一对结尾字符，只有用或不用
问题问的是长度，不是把子序列打印出来。两个串的前缀 A[0:i]、B[0:j] 一旦定了，它们的 LCS 长度就是一个数。下一对前缀只依赖更短的前缀，这是重叠子问题。
第一直觉的贪心双指针缺的是后悔权。末尾这对字符不相等时，你必须丢掉其中一个，但当时不知道丢谁更亏。把两种丢掉都算出来再取 max，才不丢最优。末尾相等时，这对字符一定可以进 LCS：不用它们不会更长，用了就回到「两个都缩短一位」的子问题再加一。
从缺口写出转移。dp[i][j] 表示 A 前 i 个字符与 B 前 j 个字符的 LCS。第 0 行第 0 列是空串，全 0。A[i−1]==B[j−1] 时走对角线 dp[i−1][j−1]+1；否则 dp[i][j]=max(dp[i−1][j], dp[i][j−1])，即删 A 尾或删 B 尾。格子只看左、上、左上，按行填即可。
用手走主例。A=abcde，B=ace，表 6 行 4 列（含空前缀）。i=1 对 a：a 对 a 得 1，对 c、对 e 继承 1，第一行数据 [0,1,1,1]。i=2 对 b：和 ace 都不等，整行仍是 [0,1,1,1]。i=3 对 c：c 对 a 仍 1，c 对 c 走左上 1+1=2，c 对 e 继承 2，行是 [0,1,2,2]。i=4 对 d：都不等，行保持 [0,1,2,2]。i=5 对 e：e 对 a 是 1，对 c 是 2，对 e 走左上 2+1=3。右下角 3，对应 ace。演示表与这一格一格的数完全一致。
连续公共子串会在不等时把长度清零，本题不等只是不加一，长度可以横向或纵向继承，所以 ace 中间跳过 b、d 仍然连得上。每个格子常数时间，O(m·n)。只要上一行，空间可压到 O(n)，但写清二维表更利于对照演示。
斜取与取 max 不能混相等必须看左上，那是「两个串都消耗这个字符」。写成 max(上,左)+1 会把单边丢掉的字符也算进公共长度。主例最后的 e 对 e，左上是 2 不是 3。
| "" | a | c | e | |
|---|---|---|---|---|
| "" | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 |
| b | 0 | 1 | 1 | 1 |
| c | 0 | 1 | 2 | 2 |
| d | 0 | 1 | 2 | 2 |
| e | 0 | 1 | 2 | 3 |
Go：LCS 表格
func longestCommonSubsequence(a, b string) int {m, n := len(a), len(b)dp := make([][]int, m+1)for i := 0; i <= m; i++ { dp[i] = make([]int, n+1) }for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if a[i-1] == b[j-1] {dp[i][j] = dp[i-1][j-1] + 1} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1])}}}return dp[m][n]}func max(a, b int) int { if a > b { return a }; return b }
1下标错开一位：dp 的 i、j 是长度，比较的是 a[i-1] 与 b[j-1]。第 0 行第 0 列保持 0。
2相等只加左上，表示这两个字符都留下。主例 e 对 e 用的是 dp[4][2]+1。
3不等取上或左的较大者，表示丢掉其中一个串的尾字符。不能清零。
4返回右下角。主例 dp[5][3]=3。
总结
LCS：相等左上加一，不等取上/左较大。主例 abcde 与 ace 右下角是 3。
- 贪心双指针在 "abc" 与 "acb" 上会走错。表记下每个前缀对的最优。
- 子序列允许跳格，所以不等时继承而不是清零。
- LC583 的最少删除就是 m+n−2·LCS。