目录一、LeetCode 1143. 最长公共子序列题目回顾核心思路二维 DPJava 实现代码二刷反思二、LeetCode 72. 编辑距离题目回顾核心思路二维 DPJava 实现代码二刷反思三、两道题的关联与 DP 思想总结继续更新我的 LeetCode 二刷复盘这次啃的是两道动态规划的经典标杆题「最长公共子序列」和「编辑距离」。比起第一次硬套 DP 模板这次终于把状态转移的底层逻辑给吃透了趁热整理成博客把关键思路和易错点沉淀下来。一、LeetCode 1143. 最长公共子序列题目回顾给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列返回 0。子序列不要求连续只要相对顺序不变即可核心思路二维 DP这道题是双序列 DP 的入门标杆核心是用二维 DP 表记录两个字符串前i和前j个字符的最长公共子序列长度。状态定义dp[i][j]表示text1[0..i-1]和text2[0..j-1]的最长公共子序列长度状态转移方程如果text1[i-1] text2[j-1]dp[i][j] dp[i-1][j-1] 1当前字符匹配子序列长度 1如果不相等dp[i][j] max(dp[i-1][j], dp[i][j-1])取两个字符串分别去掉当前字符的最大值初始化dp[0][*] 0dp[*][0] 0空字符串的公共子序列长度为 0Java 实现代码java运行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]; }二刷反思第一次写的时候只记住了转移方程却没理解为什么要这么转移。这次才明白不相等时取max本质是在 **“删除 text1 当前字符” 和 “删除 text2 当前字符” 两个决策中保留最优解 **。空间优化可以用一维数组滚动更新把空间复杂度从 O (mn) 降到 O (min (m,n))核心是倒序遍历j避免覆盖上一轮的状态。易错点数组下标和字符串下标要区分开dp[i][j]对应的是text1[i-1]和text2[j-1]很容易写错索引。二、LeetCode 72. 编辑距离题目回顾给你两个单词word1和word2请你计算出将word1转换成word2所使用的最少操作数。三种合法操作插入一个字符、删除一个字符、替换一个字符核心思路二维 DP这道题是双序列 DP 的进阶和「最长公共子序列」是一脉相承的核心是用 DP 表记录将word1前i个字符转为word2前j个字符的最少操作数。状态定义dp[i][j]表示将word1[0..i-1]转换为word2[0..j-1]的最少操作次数状态转移方程如果word1[i-1] word2[j-1]dp[i][j] dp[i-1][j-1]字符匹配无需操作如果不相等dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1分别对应dp[i-1][j] 1删除word1的当前字符dp[i][j-1] 1在word1中插入一个字符等价于删除word2的当前字符dp[i-1][j-1] 1替换word1的当前字符为word2的当前字符初始化dp[0][j] j空字符串转为word2的前j个字符需要j次插入dp[i][0] iword1的前i个字符转为空字符串需要i次删除Java 实现代码java运行public int minDistance(String word1, String word2) { int m word1.length(); int n word2.length(); int[][] dp new int[m 1][n 1]; // 初始化边界 for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j; // 状态转移 for (int i 1; i m; i) { for (int j 1; j n; j) { if (word1.charAt(i - 1) word2.charAt(j - 1)) { dp[i][j] dp[i - 1][j - 1]; } else { dp[i][j] Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1; } } } return dp[m][n]; }二刷反思第一次做的时候很容易混淆三种操作对应的状态转移。这次才彻底理清删除 / 插入 / 替换分别对应 DP 表中三个方向的状态本质是从三种操作中选择代价最小的一种。空间优化同样可以用一维数组优化空间复杂度降到 O (min (m,n))但需要额外变量保存dp[i-1][j-1]的值。易错点初始化边界时dp[i][0]和dp[0][j]不能写错否则整个 DP 表的计算都会出错。三、两道题的关联与 DP 思想总结这两道题看似不同底层的 DP 逻辑高度同源双序列 DP 的通用模板定义二维 DP 表状态表示两个字符串前i/j个字符的子问题解状态转移只依赖左、上、左上三个方向的状态初始化处理空字符串的边界情况核心区别最长公共子序列求最大值字符匹配时 1不匹配时取 max编辑距离求最小值字符匹配时直接继承不匹配时取 min1二刷的最大收获终于从 “套模板” 升级到了 “懂逻辑”以后遇到类似的双序列 DP 题比如「不同的子序列」「两个字符串的删除操作」就能快速套用这套思路而不是死记硬背。