题目描述
思路解析动画文字版
每个字符串的子序列都是指数级。二维 DP 用前缀对前缀，避免重复。
dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的 LCS 长度。
二维表定义：行是 text1 的前缀，列是 text2 的前缀。第 0 行/列代表空串。
a == a：两个当前字符相等，来自左上角加一。
b != a：字符不等，不能同时选，取上方或左方最大。
c == c：遇到 c 和 c 相等，左上角的 1 加一，变成 2。
e == e：最后 e 和 e 相等，从左上角 2 加一，得到 3。
不连续也可以：b 和 d 没被选中，但 a、c、e 的相对顺序保留，所以是子序列。
左上、上、左三个方向就是 LCS 的全部。
边界三连：空串、完全相同、完全不同，是二维 DP 初始化和转移的基本盘。
雷区实演 · 不是子串："ace" 在 "abcde" 中不连续，但它是合法子序列。最长公共子串会是 1，不是 3。
面试追问 1：从 dp[m][n] 反向走：相等走左上并收字符，不等走较大方向。
面试追问 2：只求长度时可用两行或一行滚动数组。
面试追问 3：子串要求连续，不等时通常归零；子序列不要求连续。
这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。
参考代码
class Solution: def longestCommonSubsequence(self, text1, text2): m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[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]复杂度
- 时间复杂度：O(mn)，二维表每个格子填一次
- 空间复杂度：O(mn)，基础写法保存整张表
可套用的代码模板
这一步不是复读 最长公共子序列 的参考答案，而是抽出这题真正能迁移的骨架；换题时先判断状态/容器含义，再填核心分支。
# 1. 说清 dp[状态] 的含义dp = 初始值for state in 遍历顺序: for choice in 可选动作: candidate = dp[前置状态] + 这次选择的代价 dp[state] = best(dp[state], candidate)return dp[答案状态]易错点
面试追问把动画讲成自己的话
追问怎么恢复具体 LCS？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最佳买卖股票含冷冻期
LeetCode 309 · 中等 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题