绥化市网站建设_网站建设公司_SSL证书_seo优化

问题理解

你有三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

目标：把 word1 变成 word2，用最少的操作次数。

dp思路

设 dp[i][j] 表示将 word1 的前 i 个字符 转换为 word2 的前 j 个字符 所需的最小操作数。

考虑 word1[i-1] 和 word2[j-1]（当前字符）：

1. 如果相等：word1[i-1] == word2[j-1]
   • 不需要操作，直接继承：dp[i][j] = dp[i-1][j-1]
2. 如果不等：
   • 有三种选择，取最小值 + 1：
     • 替换：dp[i-1][j-1] + 1
     • 删除（删 word1 的第 i 个）：dp[i-1][j] + 1 删除后再从word1的前i-1个字符变为word2的前j个字符。
     • 插入（在 word1 后插 word2[j-1]）：dp[i][j-1] + 1 插入后再从word1的前i个字符变为word2的前j-1个字符。
   • 所以：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

Trick

二维vector定义+初始化: vector<vector<int>> dp(m, vector<int>(n, 0)); 二维空间(m, n)初始化为0.

定义和初始化分开：

vector<vector<int>> dp;
dp.resize(l1 + 1);
for (int i = 0; i <= l1; i++) {
dp[i].resize(l2 + 1, 0); // resize可以改变形状和赋值
}

Code

class Solution {
public:int minDistance(string word1, string word2) {int l1 = word1.length(), l2 = word2.length();vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1, 0));for(int i = 0; i <= l1; i++)dp[i][0] = i;for(int j = 0; j <= l2; j++)dp[0][j] = j;for(int i = 1; i <= l1; i++)for(int j = 1; j <= l2; j++){if(word1[i - 1] == word2[j - 1])dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;}return dp[l1][l2];}
};