题型地图 56天全屏 141题

当前：LC1143 · 最长公共子序列 · 首次出现于 Day 39 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC1091已是最后一题

141 / 141回到 Day 39 卡片 141 题索引

LC1143

最长公共子序列 · Longest Common Subsequence

二维 DP

给两段字符串 text1 = "abcde" 和 text2 = "ace"，找一段两边都能按顺序拼出来的最长“暗号”。可以跳过字符，但不能改变顺序。

text1

5-3

text2

当前共同暗号

a → c → e

LCS 长度 = 3

时间 O(mn) · m=len(text1), n=len(text2)空间 O(mn) · 二维 dp 表滚动数组优化 → O(min(m,n))答案 dp[m][n] = 3

子串 vs 子序列 · 一图分清

子串 · substring需连续

在 "abcde" 里查找连续的 "ace"。中间不允许跳过任何字符。

❌ "ace" 在 "abcde" 中不是连续片段，子串视角下不存在这个公共片段。

子序列 · subsequence可跳过 · 不可乱序

从 "abcde" 按原顺序挑字符：保留 a，跳过 b，保留 c，跳过 d，保留 e。

✅ 跳过 b、d 后，剩下的 a→c→e 顺序与 "ace" 完全一致，长度 3 即 LCS。

暴力枚举为什么不行

最直白的做法：把 text1 的所有子序列（共 2^m 个）和 text2 的所有子序列（2ⁿ 个）两两比较，挑最长的公共子序列。复杂度约为 O((m+n)·2^m+n)，规模稍微大点就直接爆炸。

输入规模	暴力比较次数	DP 格子数 (m·n)
m=5, n=3（当前例子）	2^8 ≈ 256	15
m=10, n=10	2^20 ≈ 1.0×10^6	100
m=20, n=20	2^40 ≈ 1.1×10^12	400
m=100, n=100	2^200 ≈ 10^60 (爆炸)	10,000

关键观察：暴力会一遍又一遍计算同一对前缀的 LCS。下面我们要做的，就是把这些重复结果记下来，让每一对前缀只算一次——这就是 DP 的入口。

为什么必须是二维 DP

不枚举所有子序列，那就反过来问：每一步要给后面的人交付什么"进度"？

Step 1要记录什么进度？
两个字符串都在并行往前读。要避免重复计算，必须同时记下：text1 看到第几个 + text2 看到第几个。
Step 2那就要两个变量
一个变量 i 记 text1 进度，一个变量 j 记 text2 进度。一个变量管不过来——两边可以独立地"跳过 / 保留"，必须分别记。
Step 3两个变量 = 一张表
i 当行号、j 当列号，所有 (i, j) 自然铺成一张 (m+1)×(n+1) 的表格。每格存一个子问题答案，就是 DP 表。

i ∈ [0..m]×j ∈ [0..n](m+1) × (n+1) 个子问题↘ 接下来要填的整张 DP 表

一个格子代表什么 · dp[i][j] 是两个前缀

最常见的误解，是把 dp[i][j] 当成"text1 的第 i 个字符和 text2 的第 j 个字符"。它不是两个字符，是两个前缀。

举例 · dp[3][2]

text1 前 3 个

abcde

text2 前 2 个

ace

dp[3][2] 问的是 "abc" 和 "ac" 的 LCS 长度是多少。答案是 2（拼出 "ac"）。

两层 for 在做什么

外层 for i = 1..m：text1 前缀从 1 个字符一直长到 m 个字符。
内层 for j = 1..n：在每个 i 下，text2 前缀从 1 个一直长到 n 个。

两层循环 = 把表里每一对 (i, j) 都问一遍，每格只问一次、只算一次。

第 0 行 / 第 0 列代表"空串"，dp[0][*] = dp[*][0] = 0。这正是表要开成 (m+1)×(n+1) 的原因。

一个格子怎么填 · 两种情况

填 dp[i][j] 时，盯住的是两个前缀的最后一个字符：text1[i-1] 与 text2[j-1]。看它们等不等：

情况 A · 字符相等text1[i-1] == text2[j-1]

这个公共字符一定要进 LCS——不要白不要。剩下的问题，就是把它们去掉后，"前 i-1 个" 和 "前 j-1 个" 的 LCS：

dp[i][j] = dp[i-1][j-1] + 1

对应 DP 表里的 ↖ 左上 +1 箭头。

情况 B · 字符不等text1[i-1] != text2[j-1]

两个尾字符不一样，至少有一个不能进 LCS。两种放弃方式：

放弃 text1 的尾字符 → 看 dp[i-1][j]
放弃 text2 的尾字符 → 看 dp[i][j-1]

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

对应 DP 表里 ↑ 上方或 ← 左方的较大值。

基底：dp[0][*] = dp[*][0] = 0（任一侧空串，LCS 必为 0）。从左上往右下按 for 循环把整张表填完，答案就是 dp[m][n]。

Step 1 / 15

DP Grid Theater · dp[i][j] = LCS(text1 前 i 个, text2 前 j 个)

点击任意格子查看含义

∅j=0

aj=1

cj=2

ej=3

∅i=0

ai=1

bi=2

ci=3

di=4

ei=5

↖ 左上 · 字符相同 · 左上 +1↑ 上方 · 跳过 text1 当前字符← 左方 · 跳过 text2 当前字符⭐ 匹配成功（金色）

决策面板 · dp[1][1]

MATCH

text1[i-1]

'a' (i=1)

text2[j-1]

'a' (j=1)

公式

dp[1][1] = dp[0][0] + 1 = 0 + 1 = 1

自然语言

text1[0]='a' 与 text2[0]='a' 相同，把这个共同字符接到左上角的 LCS 后面，长度 +1。

当前 dp 值

Go 解法 · 与 DP 表同步

i=1 · j=1

1func longestCommonSubsequence(text1, text2 string) int {
2    m, n := len(text1), len(text2)
3    dp := make([][]int, m+1)
4    for i := range dp {
5        dp[i] = make([]int, n+1)
6    }
7    for i := 1; i <= m; i++ {
8        for j := 1; j <= n; j++ {
9            if text1[i-1] == text2[j-1] {
10                dp[i][j] = dp[i-1][j-1] + 1
11            } else {
12                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
13            }
14        }
15    }
16    return dp[m][n]
17}

紫色行 = 字符相同 · dp[i-1][j-1] + 1；蓝色行 = 字符不同 · max(上方, 左方)。

字符串时间线 · 找一组合法的“暗号”

金色字母是双方都按顺序保留下来的字符；灰色字母被跳过。两条时间线靠金色连线对齐。

text1

5-3

text2

提示：合法 LCS 不止一种，但长度只有一个 = dp[m][n]。

面试 30 秒答题模板

① 定义： dp[i][j] = text1 前 i 个字符与 text2 前 j 个字符的最长公共子序列长度。
② 转移：字符相等取左上 +1；不等时取上方与左方的较大值。
③ 初始化： dp[0][*] = dp[*][0] = 0，空串与任何串的 LCS 为 0。
④ 答案： dp[m][n]，本题只返回长度。
⑤ 复杂度：时间 O(mn)，空间 O(mn)；滚动数组可降到 O(min(m, n))。

常见误区 · 别再翻车

把子序列当子串
"ace" 不是 "abcde" 的子串（不连续），但是子序列。LCS 允许跳过字符。
误以为 dp[i][j] 是“两个字符的答案”
dp[i][j] 处理的是两个前缀，不是两个字符。i、j 是“看了几个字符”。
字符不等时为什么看上和左
至少要放弃一个尾字符。看上方=放弃 text1 末尾；看左方=放弃 text2 末尾；取较大的子问题答案。
为什么数组要开 m+1 和 n+1
第 0 行/列代表“空串”这种 base case。没有这一圈，i-1、j-1 就会越界。
返回长度，不是字符串
题目只要长度。要返回具体子序列得加回溯，且不止一种合法结果。