题目描述
求两个字符串的最长公共子序列长度(顺序一致、可不连续)。
思路解析
最直接的想法：对每个字符递归地试「让它进不进公共子序列」，两串各 2 的若干次方种组合。但「text1 前 i 个 vs text2 前 j 个」这种子问题会被反复递归很多遍。慢就慢在重复子问题。
用二维表 dp[i][j] 记「text1 前 i 个、text2 前 j 个的 LCS 长度」。转移分两种：当前两字符相等 → 等于「都去掉这字符」的左上 dp[i-1][j-1] + 1；不相等 → 取「去掉其一」的 max(上 dp[i-1][j], 左 dp[i][j-1])。为什么能记表？每个 (i,j) 子问题只算一次存进表，后面直接查——重叠子问题被压成一次。
建表 · 边界 0：表固定 6 行 4 列，行列各多一行「空串」。任一方是空串 LCS 必为 0，所以第一行、第一列全填 0。咱从左上往右下一格格填。
a 行 · a vs a 相等：第一行(text1 的 a)：a 和 text2 的 a 相等，取左上角 + 1 = 1。这行后面 a 与 c、e 都不等，各取 max(上,左) 也是 1，整行填成 1、1、1。
b 行 · 全不等(负例)：text1 的 b 在 text2 里根本没有：这是负例——字符不等，不能用左上+1，只能取较大邻格 max(上,左)。每格都从上、左抄来较大的 1，整行保持 1。
c 行 · c vs a 不等：到第三行(c)第一格：c 和 a 不等，取 max(上 1, 左 0) = 1。
c 行 · c vs c 相等 *：关键一步：c 和 c 相等，取左上 dp[2][1]=1 再 +1 = 2——公共子序列从 "a" 长成了 "ac"。第三格 c 与 e 不等，取 max(上1,左2)=2，本行成 1、2、2。
d 行 · 全不等：text1 的 d 在 text2 里也没有，又是不等的情况：每格取 max(上,左)，等于把上一行的进度 1、2、2 原样继承下来。
e 行 · 前两格不等：最后一行(e)：e 和 a 不等取 1，e 和 c 不等取 max(上2,左1)=2。接着该看最右下那格了。
e 行 · e vs e 相等 *：最后一格：e 和 e 相等，取左上 dp[4][2]=2 再 +1 = 3——公共子序列从 "ac" 长成了 "ace"。
答案 = 右下角：右下角 dp[5][3] = 3 就是答案("ace")。两次「相等 +1」攒出长度，中间一堆「不等取邻格」负责把进度传下去。
两个序列比对的题都是这套二维 DP：最长重复子数组、编辑距离、不相交的线。
参考代码（Python）
1def longestCommonSubsequence(self, text1, text2):
2 m, n = len(text1), len(text2)
3 dp = [[0]*(n+1) for _ in range(m+1)] # 多一行一列空串
4 for i in range(1, m+1):
5 for j in range(1, n+1):
6 if text1[i-1] == text2[j-1]: # 字符相等
7 dp[i][j] = dp[i-1][j-1] + 1 # 左上 +1
8 else: # 不等
9 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 上、左取大
10 return dp[m][n]复杂度分析
- 时间复杂度：O(m×n) —— 每个 (i,j) 格只算一次，共 m×n 格
- 空间复杂度：O(m×n) —— 一张二维表；每格只依赖上一行，可滚动压成两行/一行
套路模板
记住骨架：多一行一列空串、相等取左上+1、不等取上左较大。把这两条转移改一改，编辑距离、最长重复子数组、不相交的线全是它。
1# 凡是「两个序列比对」的题都套这个骨架
2dp = [[0]*(n+1) for _ in range(m+1)] # 多一行一列空串
3for i in range(1, m+1):
4 for j in range(1, n+1):
5 if A[i-1] == B[j-1]: # 相等
6 dp[i][j] = dp[i-1][j-1] + 1
7 else: # 不等
8 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
9return dp[m][n]易错点
- 错误写法：不等时也写成左上 dp[i-1][j-1]+1 → 正确写法：不等取 max(上 dp[i-1][j], 左 dp[i][j-1])（只有字符相等才能用左上 +1；不等却 +1 会凭空造出不存在的公共字符，长度偏大）
- 错误写法：字符下标用 dp 的 i、j → 正确写法：用 text1[i-1]、text2[j-1]（dp 多了「空串」那一行一列，字符下标要错开 1，否则比错字符且末尾越界）
- 错误写法：只开 m×n 不开 (m+1)×(n+1) → 正确写法：表多一行一列当空串边界（没有 0 边界，i-1/j-1 在第一格就越界）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。