【动态规划-5】72.编辑距离

题目描述给你两个单词word1和word2请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作插入一个字符删除一个字符替换一个字符示例 1输入word1 horse, word2 ros输出3解释horse - rorse (将 h 替换为 r) rorse - rose (删除 r) rose - ros (删除 e)示例 2输入word1 intention, word2 execution输出5解释intention - inention (删除 t) inention - enention (将 i 替换为 e) enention - exention (将 n 替换为 x) exention - exection (将 n 替换为 c) exection - execution (插入 u)解题思路方法一动态规划核心思路状态定义dp[i][j] 将word1的前i个字符转换成word2的前j个字符所需的最少操作数。状态转移对于word1[i-1]和word2[j-1]情况1字符相同dp[i][j] dp[i-1][j-1] 不需要操作情况2字符不同dp[i][j] 1 min( dp[i-1][j], // 删除 word1[i-1] dp[i][j-1], // 插入 word2[j-1] dp[i-1][j-1] // 替换 word1[i-1] 为 word2[j-1] )初始化dp[0][j] jword1 为空需要插入 j 个字符dp[i][0] iword2 为空需要删除 i 个字符具体过程示例word1 horse, word2 rosdp: r o s 0 1 2 3 h 1 1 2 3 o 2 2 1 2 r 3 2 2 2 s 4 3 3 2 e 5 4 4 3 dp[5][3] 3 ✅代码实现写法1二维 DPclass Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); // 初始化 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[i-1] word2[j-1]) { dp[i][j] dp[i-1][j-1]; } else { dp[i][j] 1 min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}); } } } return dp[m][n]; } };写法2一维 DP空间优化class Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorint dp(n 1, 0); // 初始化word1 为空 for (int j 0; j n; j) dp[j] j; for (int i 1; i m; i) { int prev dp[0]; // 保存 dp[i-1][j-1] dp[0] i; // dp[i][0] i for (int j 1; j n; j) { int temp dp[j]; // 保存 dp[i-1][j] if (word1[i-1] word2[j-1]) { dp[j] prev; } else { dp[j] 1 min({dp[j], dp[j-1], prev}); } prev temp; // 更新 prev } } return dp[n]; } };复杂度分析方法时间复杂度空间复杂度二维 DPO(m × n)O(m × n)一维 DPO(m × n)O(n)关键细节1. 三种操作对应哪些状态操作状态转移含义删除dp[i-1][j]删除 word1[i-1] 后用前 i-1 个字符匹配 j 个插入dp[i][j-1]插入 word2[j-1] 后用 i 个字符匹配前 j-1 个替换dp[i-1][j-1]替换 word1[i-1] 为 word2[j-1] 后匹配前 i-1 和前 j-12. 为什么字符相同时不需要操作因为word1[i-1] word2[j-1]这两个字符已经匹配只需要看前面的部分。3. 一维 DP 的prev变量prev保存的是dp[i-1][j-1]左上角的值因为dp[j-1]在当前行已经被更新了不能直接用。总结要点说明核心思想dp[i][j]表示转换的最少操作数状态转移相同dp[i-1][j-1]不同1 min(删, 插, 换)初始化dp[i][0] idp[0][j] j时间复杂度O(m × n)空间复杂度O(n)