最长公共子序列
Longest Common Subsequence
求两个字符串的最长公共子序列长度。子序列不要求连续，只要字符相对顺序一致即可。
在力扣中练习题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0 。
提示：
1 <= text1.length, text2.length <= 1000text1和text2仅由小写英文字符组成。
解题思路
二维 DP · 末尾字符分情况
比较两个前缀的最后一个字符，相同就 +1，不同就扔掉一边
子序列可以跳过字符，但保留原有相对顺序。用 dp[i][j] 表示两个前缀的最长公共子序列长度，就能把“最后一个字符要不要保留”变成局部判断。
自拟主例 text1="abca"，text2="baca" 含重复字符和错位匹配，答案为 3，例如 bca 或 aca；它们不必在两个原串中都连续。
(1,1)：'a' 不同于 'b'，取上方和左方较大值，写入 0。
dp[i][j]：text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度
dp[1][1]=max(dp[0][1], dp[1][0])max(0, 0)=0并列最优 0
末尾字符相同时，把它们一起接在左上前缀的答案之后，得到 dp[i-1][j-1]+1。不同时，至少要丢掉一边的末尾，比较上方和左方的结果，不能直接读左上。
(4,1)：'a' 不同于 'b'，取上方和左方较大值，写入 1。
dp[i][j]：text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度
dp[4][1]=max(dp[3][1], dp[4][0])max(1, 0)=1选中 dp[3][1] 上方
空串对应第 0 行和第 0 列，初值均为 0。按行从左到右填表时，三个依赖方向都已经计算完。最后返回的是两个完整前缀对应的格子，而不是表中随便一个局部匹配长度。
易错点
- 下标错位：dp 的第 i 行对应 text1[i-1]，写成 text1[i] 会越界或错配。
- dp 只开 m×n 不留哨兵行列，i-1 / j-1 就得处处特判，很容易漏。
- 把子序列当成子串：子串要求连续，失配时 dp[i][j] 要直接清零，而不是从上方 / 左方取 max。
滚动数组 · 一维 DP
每一行只依赖上一行，把二维表压成一行
正确的空间优化版，只保留上一行信息；更省空间，但不能直接保留完整的状态表。
观察转移方程：dp[i][j] 只用到 dp[i-1][j-1]、dp[i-1][j] 和 dp[i][j-1]，也就是上一行和本行左边。所以不需要保存整个表。
把二维压成一维后，dp[j] 在覆盖前是 dp[i-1][j]（上方），覆盖后是 dp[i][j]（本行）。左边格 dp[j-1] 已经更新过，可以直接用。
麻烦的是左上角 dp[i-1][j-1]：它会被覆盖掉。用一个变量 prev 记住这一轮开始前的 dp[j]：
temp = dp[j] // 旧值 = dp[i-1][j]，下一列的左上角
dp[j] = prev + 1 // 匹配时：prev 正是 dp[i-1][j-1]
prev = temp // 交给 j+1 用
空间从 O(m×n) 降到 O(n)，代价是要多想清楚 prev 的时序，写错了不会报错，只会悄悄算错。
- 1dp 数组长度 n+1，初始全 0。
- 2每行开始前 prev = 0，代表 dp[i-1][0]。
- 3temp 先存下覆盖前的 dp[j]（上方值）。
- 4相同则 dp[j] = prev + 1，否则 dp[j] = max(dp[j], dp[j-1])。
- 5prev = temp，为下一列提供左上角。
易错点
- 忘记更新 prev，所有匹配都用了错误的左上角，答案偏小。
- 把 prev = 0 提到 i 循环外面，下一行会沿用上一行末尾的残值。
- 先更新 dp[j] 再取 temp，上方值已经被覆盖，等于把 dp[i-1][j] 弄丢了。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
text1 = "abca", text2 = "baca"空串与任何前缀的 LCS 为 0，先填第 0 行和第 0 列。
dp[i][j]：text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度
dp[0][0]=0查看 C++ 代码
延伸阅读
- 子序列不要求连续，所以不匹配时可以「丢掉一边」；子串要求连续，转移就得在失配时清零（如最长重复子数组 718）。
- 编辑距离（72）是同一张二维表：匹配时不动，不匹配时在增、删、改三种操作里取最小。
- 两个字符串的 DP 几乎都是这个形状：i、j 分别指向两个前缀，讨论 `text1[i-1]` 与 `text2[j-1]` 的关系。