题目描述
思路解析
一句话答案：LeetCode 1143 最长公共子序列：开一张二维 dp 表，dp[i][j] 记两串前缀的公共子序列长度，当前字符相等就接左上角 +1、不等就取上、左较大值，右下角即答案。时间 O(m·n)、空间 O(m·n)。
最长公共子序列，为什么可以跳着挑字符
给两个字符串 text1、text2，各删掉若干字符后，找最长的公共部分。子序列是跳着挑的字符：剩下的按原顺序排好就行，不必挨着，这和「必须连续截一段」的子串不同。题面 text1 = "ABCD"、text2 = "ACBAD"，最长公共子序列长 3，比如 "ABD"。
把所有子序列都列出来，为什么算不完
把 text1 每个子序列都拼出来到 text2 里核对，长度 m 的串有 2^m 个子序列（每字符选或不选），串一长指数爆炸枚举不完。既然前缀比对被反复重验，就把「text1 前 i 个、text2 前 j 个字符的最长公共子序列多长」算一次存下来复用。
一张二维表，dp[i][j] 到底存什么
用动态规划（把「text1 前 i、text2 前 j 个字符的答案」存进表、后面直接取不重算）：dp[i][j] 就是 text1 前 i、text2 前 j 个字符的最长公共子序列长度，(i,j) 是（行号，列号）从 0 数起，一格即一个状态（推进到哪一步、手里那个答案）。表比两串各多开一圈，第 0 行、第 0 列填 0（任一串取 0 个字符时公共部分就是 0）；这圈 0 是地基，靠它每格都能直接看左上、上、左三个邻格。
相等接左上、不等取较大，凭什么是对的
表多开了一圈，dp[i][j] 里的当前两字符其实是 text1[i-1]、text2[j-1]。它俩相等时，这个公共字符能接到「两边都还没用它」那段答案后加一，而那正是斜上方 dp[i-1][j-1]，故 dp[i][j] = dp[i-1][j-1] + 1。不等时两字符不能同用，就在正上 dp[i-1][j] 与正左 dp[i][j-1] 里取较大，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。这就是递推（拿邻格推出当前格）。
拿 ABCD 和 ACBAD 逐格把表填出来
text1 = "ABCD" 作行、text2 = "ACBAD" 作列，第 0 行、第 0 列铺 0。第 1 行填 A：和 text2 的两个 A 相等、都接左上 0 得 1，其余取较大也是 1，整行 1 1 1 1 1。
第 2 行 B：第三列相等 dp[2][3] 接左上 dp[1][2]=1 得 2，整行 1 1 2 2 2。第 3 行 C 同理，整行 1 2 2 2 2。第 4 行 D：末列相等 dp[4][5] 接左上 dp[3][4]=2 得 3，整行 1 2 2 2 3。右下角 3 就是答案。
dp 下标错记成 text1[i]，整张表为什么会全错位
表满 m×n 格、每格常数时间，时间 O(m·n)（大 O 记号，描述串变长时计算量怎么涨）；空间也是一张表 O(m·n)，只求长度时每格只依赖上一行和本行左边，留两行滚着填（滚动数组：留最近几行覆盖旧值）压到 O(min(m,n))。最坑的是下标错位：dp[i][j] 对的是 text1[i-1]、text2[j-1]，写成 text1[i]、text2[j] 就整体偏一格、整张表全错。边界都被那圈 0 兜住：两串全同取到全长，空串或毫无公共都取 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条「字符相等取左上角+1，不等取上、左较大值」，下面每一格都在套它。
准备 · 边界全 0：空串行列都是 0：text1 或 text2 取 0 个字符时，公共子序列长度当然是 0。这是递推的地基，接下来从左上往右下、一行一行填内部的格子。
填 dp[1][1] · A vs A：当前格 dp[1][1]：text1 的 A 和 text2 的 A 相等！可以在左上角 dp[0][0]=0 的基础上接长一位 → 填 1。
填 dp[1][2] · A vs C：当前格 dp[1][2]：text1 的 A 和 text2 的 C 不等，这两个字符不能同时用。取上面 0 和左边 1 里较大的 → 填 1。
填 dp[1][3] · A vs B：当前格 dp[1][3]：text1 的 A 和 text2 的 B 不等，这两个字符不能同时用。取上面 0 和左边 1 里较大的 → 填 1。
填 dp[1][4] · A vs A：当前格 dp[1][4]：text1 的 A 和 text2 的 A 相等！可以在左上角 dp[0][3]=0 的基础上接长一位 → 填 1。
填 dp[1][5] · A vs D：当前格 dp[1][5]：text1 的 A 和 text2 的 D 不等，这两个字符不能同时用。取上面 0 和左边 1 里较大的 → 填 1。
填 dp[2][1] · B vs A：当前格 dp[2][1]：text1 的 B 和 text2 的 A 不等，这两个字符不能同时用。取上面 1 和左边 0 里较大的 → 填 1。
填 dp[2][2] · B vs C：当前格 dp[2][2]：text1 的 B 和 text2 的 C 不等，这两个字符不能同时用。取上面 1 和左边 1 里较大的 → 填 1。
填 dp[2][3] · B vs B：当前格 dp[2][3]：text1 的 B 和 text2 的 B 相等！可以在左上角 dp[1][2]=1 的基础上接长一位 → 填 2。
填 dp[2][4] · B vs A：当前格 dp[2][4]：text1 的 B 和 text2 的 A 不等，这两个字符不能同时用。取上面 1 和左边 2 里较大的 → 填 2。
填 dp[2][5] · B vs D：当前格 dp[2][5]：text1 的 B 和 text2 的 D 不等，这两个字符不能同时用。取上面 1 和左边 2 里较大的 → 填 2。
填 dp[3][1] · C vs A：当前格 dp[3][1]：text1 的 C 和 text2 的 A 不等，这两个字符不能同时用。取上面 1 和左边 0 里较大的 → 填 1。
填 dp[3][2] · C vs C：当前格 dp[3][2]：text1 的 C 和 text2 的 C 相等！可以在左上角 dp[2][1]=1 的基础上接长一位 → 填 2。
填 dp[3][3] · C vs B：当前格 dp[3][3]：text1 的 C 和 text2 的 B 不等，这两个字符不能同时用。取上面 2 和左边 2 里较大的 → 填 2。
填 dp[3][4] · C vs A：当前格 dp[3][4]：text1 的 C 和 text2 的 A 不等，这两个字符不能同时用。取上面 2 和左边 2 里较大的 → 填 2。
填 dp[3][5] · C vs D：当前格 dp[3][5]：text1 的 C 和 text2 的 D 不等，这两个字符不能同时用。取上面 2 和左边 2 里较大的 → 填 2。
填 dp[4][1] · D vs A：当前格 dp[4][1]：text1 的 D 和 text2 的 A 不等，这两个字符不能同时用。取上面 1 和左边 0 里较大的 → 填 1。
填 dp[4][2] · D vs C：当前格 dp[4][2]：text1 的 D 和 text2 的 C 不等，这两个字符不能同时用。取上面 2 和左边 1 里较大的 → 填 2。
填 dp[4][3] · D vs B：当前格 dp[4][3]：text1 的 D 和 text2 的 B 不等，这两个字符不能同时用。取上面 2 和左边 2 里较大的 → 填 2。
填 dp[4][4] · D vs A：当前格 dp[4][4]：text1 的 D 和 text2 的 A 不等，这两个字符不能同时用。取上面 2 和左边 2 里较大的 → 填 2。
填 dp[4][5] · D vs D：当前格 dp[4][5]：text1 的 D 和 text2 的 D 相等！可以在左上角 dp[3][4]=2 的基础上接长一位 → 填 3。
填表完成：整张表填完！最右下角 dp[4][5] = 3 就是 text1 全部和 text2 全部的最长公共子序列长度。从这格沿着「相等就走左上、不等就走较大邻格」回溯，还能还原出具体的公共子序列。
边界先想清：完全相同取全长、毫无公共取 0、空串取 0——这些都被「多一圈 0 的边界」自然兜住。
三个高频追问：还原具体序列、滚动数组优化、以及子序列 vs 子串的差别。
参考代码
def longestCommonSubsequence(text1, text2): m, n = len(text1), len(text2) dp = [[0]*(n+1) for _ in range(m+1)] # 多一圈 0 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 # 相等:左上+1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 不等:取大 return dp[m][n] # 右下角即答案复杂度
- 时间：O(m·n)，表有 m×n 个格子，每格 O(1) 推出
- 空间：O(m·n)，存整张表；可滚动数组优化到 O(min(m,n))
易错点
面试追问把动画讲成自己的话
追问怎么还原出具体的公共子序列（而不只是长度）？
追问空间能不能优化？
追问和「最长公共子串」有什么区别？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最佳买卖股票含冷冻期
LeetCode 309 · 中等 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题