#1143
中等
高频
动态规划最长公共子序列
这是一道围绕字符串展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
字符串
题目分析
给你两个字符串，要求找出它们的最长公共子序列长度。
子序列不要求连续，只要求相对顺序保持一致。
比如 abcde 和 ace 的最长公共子序列是 ace，长度为 3。
一句话概括：
比较两个字符串的前缀，逐步推出它们的最长公共子序列长度。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：用二维 DP 表示两个前缀的最长公共子序列长度，字符相等时接左上角，不等时取上方和左方最大值。
推荐代码
推荐解法：动态规划
时间复杂度： O(m*n)
空间复杂度： O(m*n)
核心思路： 用二维 DP 表示两个前缀的最长公共子序列长度，字符相等时接左上角，不等时取上方和左方最大值。
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int 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];
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用二维 DP，把问题定义成两个字符串前缀之间的最优值。
核心过程
- 定义
dp[i][j]为两个前缀的最长公共子序列长度。 - 如果当前字符相等，就接左上角加一。
- 如果不相等，就在上方和左方状态里取更大值。
- 最终
dp[m][n]就是整个问题的答案。
复杂度总结
时间复杂度 O(m*n)，空间复杂度 O(m*n)。
面试补一句：两个字符串 DP 题先想清楚“前缀状态”通常就找到入口了。
核心思路
LCS 的关键是把问题拆成两个前缀。当前字符相等时，答案可以由更短前缀自然延长；不相等时，就只能丢掉其中一个字符继续比较。
步骤讲解
1
定义二维状态
令 dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度。
为什么这样做：两个字符串题通常都适合用“前缀对前缀”的 DP 定义。
对应代码提示：int[][] dp = new int[m + 1][n + 1];
2
字符相等时接左上角
如果当前两个字符相等，就把 dp[i - 1][j - 1] + 1 作为当前值。
为什么这样做：相等字符可以同时纳入公共子序列长度。
对应代码提示：dp[i][j] = dp[i - 1][j - 1] + 1;
3
字符不等时取上方或左方最大值
若当前字符不同，就在“丢掉 text1 当前字符”和“丢掉 text2 当前字符”之间取更优。
为什么这样做：当前这两个字符不能同时进入同一条公共子序列。
对应代码提示：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
易错点
把子串和子序列混淆
LCS 允许跳过字符，不要求连续，转移逻辑和最长公共子串完全不同。
正确理解：明确这里比较的是子序列，可以跳字符。
字符下标和 DP 下标错位
DP 表多开了一行一列，访问字符时容易写成 i、j 而不是 i - 1、j - 1。
正确理解：字符访问统一写成
text1.charAt(i - 1) 和 text2.charAt(j - 1)。字符不等时错误地取左上角
左上角只适用于两个字符都被同时使用的情况。
正确理解：字符不等时只能取上方和左方的较大值。
复杂度与适用判断
时间复杂度：O(m*n)
空间复杂度：O(m*n)
比其他方案更好在哪里：比暴力枚举所有子序列可行得多，也是这类双串问题最稳定的标准解。
适用判断：两个字符串同时出现，且目标是最长/最优匹配时，优先考虑二维前缀 DP。
额外提醒
- 相等看左上角，不等看上和左，是 LCS 最核心的转移模式。
动画演示
如果你还没完全看懂，可以展开动画演示。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
当前位置
-
当前LCS长度
0
处理进度
-47%
动态规划表
操作日志
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。