引言动态规划中有一类经典问题叫做「序列匹配」而「最长公共子序列」Longest Common Subsequence, LCS正是其中最基础、最常考的代表。给定两个字符串在不改变字符相对顺序的前提下找到它们共同拥有的最长子序列的长度。这道题与「最小路径和」一样都采用二维 DP 表格但状态转移的逻辑截然不同——它不是取最小而是根据字符是否相等来决定是否继承并加一。本文将带你从 DP 表格构造到代码实现一步步掌握这道面试常考题。摘要本文详细解析力扣 LCR 095. 最长公共子序列的动态规划解法。给定两个字符串text1和text2求它们的最长公共子序列长度。定义dp[i][j]为text1前i个字符和text2前j个字符的 LCS 长度。转移方程为若text1[i-1] text2[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])。重点讲解 DP 表格的构造过程从空串开始推导、边界初始化第一行和第一列全为 0以及为什么字符相等时一定要匹配。提供二维数组和 O(min(m,n)) 空间优化两种代码时间复杂度 O(m×n)。目录一、题目描述二、动态规划思路1. 为什么用 DP2. DP 数组的定义3. DP 数组的构造以示例 1 为例4. 状态转移方程三、Java 代码实现四、代码优化空间压缩五、易错点总结特别重要⚠️ 注意点 1dp 数组大小是 (m1)×(n1)⚠️ 注意点 2字符比较时下标要减 1⚠️ 注意点 3字符相等时为什么是 dp[i-1][j-1]1⚠️ 注意点 4空间优化时一维数组的含义六、复杂度分析总结一、题目描述给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列返回 0。子序列定义由原字符串在不改变字符相对顺序的情况下删除某些字符也可以不删除后组成的新字符串。例如ace是abcde的子序列aec不是abcde的子序列示例 1输入text1 abcde, text2 ace 输出3 解释最长公共子序列是 ace长度为 3示例 2输入text1 abc, text2 abc 输出3 解释最长公共子序列是 abc长度为 3示例 3输入text1 abc, text2 def 输出0 解释两个字符串没有公共子序列返回 0提示1 text1.length, text2.length 1000text1和text2仅由小写英文字符组成二、动态规划思路1. 为什么用 DP求text1前 i 个字符和text2前 j 个字符的 LCS 长度只依赖于三种情况如果最后一个字符相等那它一定在 LCS 中答案是dp[i-1][j-1] 1如果最后一个字符不相等要么舍弃text1的最后一个字符要么舍弃text2的最后一个字符取两者较大值这就是最优子结构——大问题的最优解包含子问题的最优解适合用 DP 自底向上推导。2. DP 数组的定义dp[i][j]text1的前i个字符与text2的前j个字符的最长公共子序列长度。注意这里i和j表示前缀长度不是下标。dp[0][j]表示text1为空串dp[i][0]表示text2为空串。3. DP 数组的构造以示例 1 为例输入text1 abcde text2 ace第一步初始化 dp 数组dp 数组大小为(m1) × (n1)其中m 5, n 3。第一行dp[0][j] 0text1为空串任何字符串的公共子序列长度都是 0第一列dp[i][0] 0text2为空串任何字符串的公共子序列长度都是 0初始化后的 dp 数组dpj0 (空串)j1 (a)j2 (c)j3 (e)i0 (空串)0000i1 (a)0待推导待推导待推导i2 (b)0待推导待推导待推导i3 (c)0待推导待推导待推导i4 (d)0待推导待推导待推导i5 (e)0待推导待推导待推导第二步从 (1,1) 开始递推双层循环核心规则比较text1[i-1]和text2[j-1]如果相等dp[i][j] dp[i-1][j-1] 1如果不相等dp[i][j] max(dp[i-1][j], dp[i][j-1])逐格推导i1, text1[0]aj1, text2[0]a相等 →dp[1][1] dp[0][0] 1 1j2, text2[1]ca≠c →dp[1][2] max(dp[0][2]0, dp[1][1]1) 1j3, text2[2]ea≠e →dp[1][3] max(dp[0][3]0, dp[1][2]1) 1i2, text1[1]bj1, b≠a →dp[2][1] max(dp[1][1]1, dp[2][0]0) 1j2, b≠c →dp[2][2] max(dp[1][2]1, dp[2][1]1) 1j3, b≠e →dp[2][3] max(dp[1][3]1, dp[2][2]1) 1i3, text1[2]cj1, c≠a →dp[3][1] max(dp[2][1]1, dp[3][0]0) 1j2, cc →dp[3][2] dp[2][1] 1 2j3, c≠e →dp[3][3] max(dp[2][3]1, dp[3][2]2) 2i4, text1[3]dj1, d≠a →dp[4][1] max(dp[3][1]1, dp[4][0]0) 1j2, d≠c →dp[4][2] max(dp[3][2]2, dp[4][1]1) 2j3, d≠e →dp[4][3] max(dp[3][3]2, dp[4][2]2) 2i5, text1[4]ej1, e≠a →dp[5][1] max(dp[4][1]1, dp[5][0]0) 1j2, e≠c →dp[5][2] max(dp[4][2]2, dp[5][1]1) 2j3, ee →dp[5][3] dp[4][2] 1 3完整 dp 数组dpj0j1 (a)j2 (c)j3 (e)i00000i1 (a)0111i2 (b)0111i3 (c)0122i4 (d)0122i5 (e)0123最终答案dp[5][3] 34. 状态转移方程边界情况空串dp[0][j] 0 (text1 为空) dp[i][0] 0 (text2 为空)通用情况i ≥ 1, j ≥ 1if 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])三、Java 代码实现class Solution { public int longestCommonSubsequence(String text1, String text2) { // 1. 获取两个字符串的长度 int m text1.length(); int n text2.length(); // 2. 创建 dp 数组 (m1) × (n1)默认值全为 0 int[][] dp new int[m 1][n 1]; // 3. 边界已自动初始化为 0dp[0][j] 和 dp[i][0] 都是 0 // 无需额外初始化 // 4. 开始动态规划的核心代码填充 dp 数组 for (int i 1; i m; i) { for (int j 1; j n; j) { // 比较 text1 的第 i 个字符和 text2 的第 j 个字符 // 注意dp 的下标 i 对应字符串的 i-1 if (text1.charAt(i - 1) text2.charAt(j - 1)) { // 字符相等继承左上角 1 dp[i][j] dp[i - 1][j - 1] 1; } else { // 字符不等取上方和左方的较大值 dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]); } } } // 5. 返回结果 return dp[m][n]; } }运行结果四、代码优化空间压缩因为dp[i][j]只依赖于左上方dp[i-1][j-1]需要上一行的旧值上方dp[i-1][j]上一行当前列左方dp[i][j-1]当前行前一列已更新所以可以用一维数组滚动更新空间复杂度降至O(n)class Solution { public int longestCommonSubsequence(String text1, String text2) { int m text1.length(); int n text2.length(); // 让 n 为较小的那个减少空间 if (m n) { // 交换 text1 和 text2保证 text2 更短 String temp text1; text1 text2; text2 temp; int tempLen m; m n; n tempLen; } int[] dp new int[n 1]; // 默认全为 0 for (int i 1; i m; i) { int prev 0; // 相当于 dp[i-1][j-1]初始为 dp[i-1][0] for (int j 1; j n; j) { int temp dp[j]; // 保存当前 dp[j] 作为下一轮的 prev if (text1.charAt(i - 1) text2.charAt(j - 1)) { dp[j] prev 1; } else { dp[j] Math.max(dp[j], dp[j - 1]); // dp[j]旧值代表上方 dp[i-1][j] // dp[j-1]新值代表左方 dp[i][j-1] } prev temp; // 更新 prev 为这一轮的 dp[j] 旧值 } } return dp[n]; } }优化要点先比较m和n让text2是较短的那个减少一维数组大小prev变量保存左上角的值dp[i-1][j-1]temp暂存dp[j]的旧值供下一轮使用五、易错点总结特别重要⚠️ 注意点 1dp 数组大小是 (m1)×(n1)很多同学会写成new int[m][n]导致无法表示空串的情况。正确做法数组大小必须是(m1) × (n1)其中dp[0][j]和dp[i][0]都为 0表示空串与任意字符串的 LCS 长度为 0。⚠️ 注意点 2字符比较时下标要减 1dp[i][j]表示前i个和前j个字符所以比较的是text1.charAt(i - 1)和text2.charAt(j - 1)错误示范写成text1.charAt(i)会导致数组越界或逻辑错误。⚠️ 注意点 3字符相等时为什么是 dp[i-1][j-1]1当text1[i-1] text2[j-1]时这两个字符一定能成为 LCS 的最后一个字符。为什么不考虑max(dp[i-1][j], dp[i][j-1]) 1因为dp[i-1][j-1]是这两个字符都不包含时的最优解把当前相等字符加在末尾必然能得到更优解。而dp[i-1][j]或dp[i][j-1]已经包含了其中一个当前字符再加当前相等字符会重复计算或破坏子序列的定义。⚠️ 注意点 4空间优化时一维数组的含义滚动数组版本中dp[j]在更新前代表上一行(i-1, j)的值更新后代表当前行(i, j)的值。关键变量prev保存dp[i-1][j-1]左上角dp[j]更新前保存dp[i-1][j]上方dp[j-1]已更新保存dp[i][j-1]左方所以Math.max(dp[j], dp[j-1])正好对应max(dp[i-1][j], dp[i][j-1])。六、复杂度分析版本时间复杂度空间复杂度二维数组O(m × n)O(m × n)一维滚动数组O(m × n)O(min(m, n))时间复杂度双层循环遍历所有 m×n 个状态每个状态 O(1) 转移空间复杂度优化后只需保存一行较短字符串长度 1总结这道题是动态规划中序列匹配类问题的入门经典核心思想是定义状态dp[i][j]表示两个字符串前缀的 LCS 长度初始化边界空串与任何字符串的 LCS 长度都是 0状态转移根据当前字符是否相等决定是匹配并加一还是舍弃一个字符最终答案dp[m][n]相比「最小路径和」本题的转移逻辑从取最小变成了字符匹配时的继承与扩展但二者都体现了 DP 的核心思想——将大问题分解为重叠子问题通过填表避免重复计算。掌握这道题后可以继续挑战「编辑距离」LeetCode 72增加了替换、插入、删除三种操作「最长公共子串」要求连续转移逻辑略有不同「两个字符串的删除操作」LeetCode 583LCS 的变形希望这篇文章能帮助你更好地理解动态规划如果有问题欢迎留言讨论