二刷 LeetCode：动态规划经典双题复盘
目录
一、LeetCode 1143. 最长公共子序列
题目回顾
核心思路（二维 DP）
Java 实现代码
二刷反思
二、LeetCode 72. 编辑距离
题目回顾
核心思路（二维 DP）
Java 实现代码
二刷反思
三、两道题的关联与 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][*] = 0，dp[*][0] = 0（空字符串的公共子序列长度为 0）
Java 实现代码
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] = i：word1的前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个字符的子问题解 - 状态转移只依赖左、上、左上三个方向的状态
- 初始化处理空字符串的边界情况
- 定义二维 DP 表，状态表示两个字符串前
- 核心区别：
- 最长公共子序列：求最大值，字符匹配时 + 1，不匹配时取 max
- 编辑距离：求最小值，字符匹配时直接继承，不匹配时取 min+1
- 二刷的最大收获：终于从 “套模板” 升级到了 “懂逻辑”，以后遇到类似的双序列 DP 题（比如「不同的子序列」「两个字符串的删除操作」），就能快速套用这套思路，而不是死记硬背。