LeetCode 1143中等动态规划 · LCS
最长公共子序列 图解题解
这道题到底在问什么
给两个字符串，求它们最长公共子序列的长度。
- text1
- "abcde"
- text2
- "ace"
- 输出
- 3，即 "ace"
最优解：一步一步想明白
- 3每个字符串的子序列都是指数级。二维 DP 用前缀对前缀，避免重复。
- 4dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的 LCS 长度。
- 5state行是 text1 的前缀，列是 text2 的前缀。第 0 行/列代表空串。
- 6match两个当前字符相等，来自左上角加一。
- 7no match字符不等，不能同时选，取上方或左方最大。
- 8match c遇到 c 和 c 相等，左上角的 1 加一，变成 2。
- 9answer最后 e 和 e 相等，从左上角 2 加一，得到 3。
- 10subsequenceb 和 d 没被选中，但 a、c、e 的相对顺序保留，所以是子序列。
- 13左上、上、左三个方向就是 LCS 的全部。
- 16not substring"ace" 在 "abcde" 中不连续，但它是合法子序列。最长公共子串会是 1，不是 3。
- 23这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。
⚠️ 容易写错的地方
✗ 错：把子序列当子串
✓ 对：允许不连续，但顺序不能变
LCS 不是最长公共子串。
✗ 错：相等时还取 max(up,left)
✓ 对：相等用左上 + 1
当前两个字符可以同时贡献一个长度。
✗ 错：下标从 0 硬写很乱
✓ 对：dp 开 m+1、n+1
第 0 行列处理空串，转移更稳。
完整代码（Python / C++ / Java）
Python
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]C++
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
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];
}
};Java
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
}套路模板 · 最长公共子序列迁移骨架
# 1. 说清 dp[状态] 的含义
dp = 初始值
for state in 遍历顺序:
for choice in 可选动作:
candidate = dp[前置状态] + 这次选择的代价
dp[state] = best(dp[state], candidate)
return dp[答案状态]// 1. 先定义 dp[state] 的含义
vector<int> dp(状态数, 初始值);
for (auto state : 遍历顺序) {
for (auto choice : 可选动作) {
auto candidate = dp[前置状态] + 代价;
dp[state] = best(dp[state], candidate);
}
}
return dp[答案状态];// 1. 先定义 dp[state] 的含义
int[] dp = new int[状态数];
Arrays.fill(dp, 初始值);
for (State state : 遍历顺序) {
for (Choice choice : 可选动作) {
int candidate = dp[前置状态] + 代价;
dp[state] = best(dp[state], candidate);
}
}
return dp[答案状态];复杂度
时间复杂度
O(mn)
二维表每个格子填一次
空间复杂度
O(mn)
基础写法保存整张表
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最长公共子序列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么恢复具体 LCS？+
从 dp[m][n] 反向走：相等走左上并收字符，不等走较大方向。
这道题为什么用「LCS」，换最直接的暴力解会差在哪？+
LCS抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。