【多维动态规划】LC 72.编辑距离

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接72.编辑距离2、题目描述二、个人思路整理1、思路分析核心思路二维动态规划状态定义设dp[i][j]表示将word1的前i个字符即下标0到i - 1转换成word2的前j个字符即下标0到j - 1所需要的最少操作数。状态转移方程考虑word1[i - 1]与word2[j - 1]的匹配情况如果字符相等word1[i - 1] word2[j - 1]当前字符不需要任何额外操作直接继承前一个状态d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] dp[i][j] dp[i - 1][j - 1]dp[i][j]dp[i−1][j−1]如果字符不相等word1[i - 1] ! word2[j - 1]可以通过以下三种操作之一完成转换取三者的最小值加 1插入字符在word1末尾插入与word2[j - 1]相同的字符等价于先将word1[0...i-1]变成word2[0...j-2]再插入该字符d p [ i ] [ j − 1 ] 1 dp[i][j - 1] 1dp[i][j−1]1删除字符将word1[i - 1]删掉等价于看word1[0...i-2]变成word2[0...j-1]的代价d p [ i − 1 ] [ j ] 1 dp[i - 1][j] 1dp[i−1][j]1替换字符将word1[i - 1]替换为word2[j - 1]等价于看word1[0...i-2]变成word2[0...j-2]的代价d p [ i − 1 ] [ j − 1 ] 1 dp[i - 1][j - 1] 1dp[i−1][j−1]1综合转移方程d p [ i ] [ j ] min ⁡ ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] ) 1 dp[i][j] \min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) 1dp[i][j]min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])1边界条件初始化dp[i][0] i当word2为空字符串时需要将word1的前i个字符全部删除代价为i。dp[0][j] j当word1为空字符串时需要插入j个字符变成word2代价为j。2、解题代码classSolution{public:intminDistance(string word1,string word2){intmword1.size();intnword2.size();// dp[i][j] 表示将 word1 的前 i 个字符 word[0...i-1]// 转换成 word2 的前 j 个字符word2[0...j-1]所需的最少操作数vectorvectorintdp(m1,vectorint(n1,0));// 边界条件初始化// 当 word2 为空字符串时需要将 word1 的前 i 个字符全部删除for(inti0;im;i){dp[i][0]i;}// 当 word1 为空字符串时需要插入 j 个字符转成 word2 的前 j 个字符for(intj0;jn;j){dp[0][j]j;}// 状态转移for(inti1;im;i){for(intj1;jn;j){// 如果末尾字符相同则不需要额外操作直接继承前一个状态if(word1[i-1]word2[j-1]){dp[i][j]dp[i-1][j-1];}else{// 若字符不同从三种可能的操作中取最小值并 1// 1. dp[i - 1][j] 1 删除 word1[i-1]// 2. dp[i][j - 1] 1 插入 word2[j-1] 到 word1// 3. dp[i - 1][j - 1] 1 将 word1[i-1] 替换为 word2[j-1]dp[i][j]min({dp[i-1][j]1,dp[i][j-1]1,dp[i-1][j-1]1});}}}// 最终返回 word1 完整转换到 word2 所需的最少操作数returndp[m][n];}};复杂度分析时间复杂度O ( m × n ) O(m \times n)O(m×n)需要遍历填充大小为( m 1 ) × ( n 1 ) (m 1) \times (n 1)(m1)×(n1)的二维表格。空间复杂度O ( m × n ) O(m \times n)O(m×n)。由于每一行只依赖于上一行和当前行的左侧值空间可以进一步优化到O ( n ) O(n)O(n)。三、知识风暴动态规划Dynamic Programming是本题的核心算法思想。它通过将原问题拆解为若干重叠子问题并利用「最优子结构」性质用子问题的最优解递推得到全局最优解。对于「编辑距离」这类求最少操作数的动态规划问题动态规划能以O ( m × n ) O(m \times n)O(m×n)的复杂度高效求解。算法核心思想最优子结构将word1的前i ii个字符转换成word2的前j jj个字符所需的最少操作数可以由「前i − 1 i - 1i−1个字符转前j − 1 j - 1j−1个字符」「前i ii个字符转前j − 1 j - 1j−1个字符」「前i − 1 i - 1i−1个字符转前j jj个字符」三种子问题的结果共同决定。只要子问题d p [ i − 1 ] [ j − 1 ] dp[i - 1][j - 1]dp[i−1][j−1]、d p [ i ] [ j − 1 ] dp[i][j - 1]dp[i][j−1]、d p [ i − 1 ] [ j ] dp[i - 1][j]dp[i−1][j]已知就能递推得到当前位置的最优解。重叠子问题在递推过程中同一个状态d p [ i ] [ j ] dp[i][j]dp[i][j]会被多个后续状态反复引用。例如计算d p [ i 1 ] [ j ] dp[i 1][j]dp[i1][j]、d p [ i ] [ j 1 ] dp[i][j 1]dp[i][j1]与d p [ i 1 ] [ j 1 ] dp[i 1][j 1]dp[i1][j1]时都会访问d p [ i ] [ j ] dp[i][j]dp[i][j]的状态因此用二维表格缓存结果可避免重复计算。与贪心的区别贪心每一步只做当前最优选择、不回溯而动态规划会枚举「插入」「删除」「替换」三种可能的操作来源从而保证结果的正确性。常见对比动态规划 vs 贪心动态规划时间复杂度O ( m × n ) O(m \times n)O(m×n)空间复杂度O ( n ) O(n)O(n)滚动数组优化后。适合需要同时考虑「插入/删除/替换」三种决策、且局部最优不能直接决定全局最优的场景通用性更强。贪心算法时间复杂度O ( m n ) O(m n)O(mn)空间复杂度O ( 1 ) O(1)O(1)。适合每一步的局部最优能直接推导全局最优的场景代码简洁高效但本题中操作选择无法用贪心直接证明例如到达某个字符时贪心只选当前「代价更小」的操作就可能错过最终最优解。共同点两者都依赖「最优子结构」性质。区别在于贪心只保留一个当前最优状态而动态规划需要同时维护「插入」「删除」「替换」三种来源的状态。动态规划的设计思想核心思想把大问题拆成小问题先解决小问题再用小问题的答案拼出大问题的答案。本题中先初始化第一行与第一列对应空串转换的边界情况再逐个字符递推出后续位置的状态。与本题的联系编辑距离问题天然具有递推结构——每个状态d p [ i ] [ j ] dp[i][j]dp[i][j]的最优解都可以由「跳过当前字符」「插入一个字符」「删除一个字符」三种来源共同得到。因此无需回溯或搜索只需按顺序填充二维表格即可。注意事项动态规划的正确性依赖于「最优子结构」与「无后效性」。本题中d p [ i ] [ j ] dp[i][j]dp[i][j]只由d p [ i − 1 ] [ j − 1 ] dp[i - 1][j - 1]dp[i−1][j−1]、d p [ i ] [ j − 1 ] dp[i][j - 1]dp[i][j−1]、d p [ i − 1 ] [ j ] dp[i - 1][j]dp[i−1][j]三个前置状态决定与未来的状态无关因此递推顺序合法。使用要点状态变量dp[i][j]记录将word1的前i ii个字符转换成word2的前j jj个字符所需的最少操作数0 ≤ i ≤ m 0 \le i \le m0≤i≤m0 ≤ j ≤ n 0 \le j \le n0≤j≤n。初始化dp[i][0] i将word1的前i ii个字符全部删除变为空串、dp[0][j] j从空串插入j jj个字符变为word2的前j jj个字符以「空串边界」作为递推基准。转移时机外层循环遍历word1的每个字符i ii内层循环遍历word2的每个字符j jj。若word1[i - 1] word2[j - 1]则直接继承dp[i - 1][j - 1]否则取「删除」「插入」「替换」三种操作的最小值加 1。结果返回遍历结束后返回dp[m][n]表示将完整的word1转换成完整的word2所需的最少操作数。算法变体与扩展不同的子序列LeetCode 115将「最少操作数」改为「不同转换方式的数量」状态转移方程由取最小值改为累加与本题的递推结构高度相似。两个字符串的删除操作LeetCode 583只允许「删除」操作不允许「插入」与「替换」是本题的一种简化变体。最长公共子序列LeetCode 1143与编辑距离同属「双串动态规划」经典题目通过维护两个字符串的前缀状态来刻画匹配关系。正则表达式匹配LeetCode 10在编辑距离基础上引入「通配符」约束需要同时考虑「匹配」「跳过」等多种情形。相关 LeetCode 例题115. 不同的子序列双串 计数583. 两个字符串的删除操作双串 删除1143. 最长公共子序列双串 匹配10. 正则表达式匹配双串 通配符