题目描述
求两个字符串的最长公共子序列长度(顺序一致、可不连续)。
text1 = "abc"
text2 = "ac"
输出 = 2 （"ac"）
思路解析
两种情况：当前两个字符相等 → 等于「都去掉这个字符」的 dp[i-1][j-1] + 1；不相等 → 取「去掉其一」的 max(dp[i-1][j], dp[i][j-1])。
建表 · 边界 0：行和列各多一行「空串」。任一方是空串，LCS 必为 0，所以第一行第一列全填 0。
a vs a · 相等：text1 的 a 和 text2 的 a 相等：取左上角 + 1 = 1。
a vs c · 不等：a 和 c 不相等：取上面和左边的较大值，得 1。
b 行 · 都不等：b 这一行，和 a、c 都不相等，每格都取 max(上,左)，一直保持 1。
c vs a · 不等：c 和 a 不等，dp[3][1] = max(上1, 左0) = 1。
c vs c · 相等 ⭐：c 和 c 相等：左上角 dp[2][1]=1 再 +1 = 2。
答案 = 右下角：右下角 dp[3][2] = 2 就是答案（"ac"）。
两个序列比对的题都是这套二维 DP：最长重复子数组、编辑距离、不相交的线。
参考代码（Python）
Python
1dp = [[0]*(n+1) for _ in range(m+1)] # 多一行一列空串
2for i in range(1, m+1):
3 for j in range(1, n+1):
4 if text1[i-1] == text2[j-1]: # 字符相等
5 dp[i][j] = dp[i-1][j-1] + 1 # 左上 +1
6 else: # 不等
7 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 上、左取大
8return dp[m][n]复杂度分析
- 时间复杂度：O(m×n) —— 填满表格
- 空间复杂度：O(m×n) —— 二维表；可压成两行
套路模板
记住骨架：多一行一列空串、相等取左上+1、不等取上左较大。把这两条转移改一改，编辑距离、最长重复子数组、不相交的线全是它。
Python
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][j] 的 i,j → ✅ 用 text1[i-1]、text2[j-1]（dp 多了「空串」那一行一列，要错开 1）
- ❌ 不等时写成左上 → ✅ 不等取 max(上, 左)（只有相等才能用左上 +1）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。