企业官网建设流程全解析

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

72.编辑距离

2、题目描述

二、个人思路整理

1、思路分析

核心思路：二维动态规划

1. 状态定义
   设dp[i][j]表示将word1的前i个字符（即下标0到i - 1）转换成word2的前j个字符（即下标0到j - 1）所需要的最少操作数。
2. 状态转移方程
   考虑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：
     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
     2. 删除字符：将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
     3. 替换字符：将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
3. 边界条件（初始化）
   • dp[i][0] = i：当word2为空字符串时，需要将word1的前i个字符全部删除，代价为i。
   • dp[0][j] = j：当word1为空字符串时，需要插入j个字符变成word2，代价为j。

2、解题代码

classSolution{public:intminDistance(string word1,string word2){intm=word1.size();intn=word2.size();// dp[i][j] 表示将 word1 的前 i 个字符 （word[0...i-1]）// 转换成 word2 的前 j 个字符（word2[0...j-1]）所需的最少操作数vector<vector<int>>dp(m+1,vector<int>(n+1,0));// 边界条件初始化// 当 word2 为空字符串时，需要将 word1 的前 i 个字符全部删除for(inti=0;i<=m;i++){dp[i][0]=i;}// 当 word1 为空字符串时，需要插入 j 个字符转成 word2 的前 j 个字符for(intj=0;j<=n;j++){dp[0][j]=j;}// 状态转移for(inti=1;i<=m;i++){for(intj=1;j<=n;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)(m+1)×(n+1)的二维表格。
• 空间复杂度：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[i+1][j]、d p [ i ] [ j + 1 ] dp[i][j + 1]dp[i][j+1]与d p [ i + 1 ] [ j + 1 ] dp[i + 1][j + 1]dp[i+1][j+1]时，都会访问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(m+n)，空间复杂度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≤m，0 ≤ 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. 正则表达式匹配（双串 + 通配符）