583 两个字符串的删除操作

思路：算法使用一个二维矩阵 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作次数。在初始化时，将 dp[i][0] 和 dp[0][j] 分别设置为 i 和 j，因为将一个字符串转换为空字符串的最小操作次数等于字符串长度。

然后，算法对 word1 和 word2 进行迭代，填充 dp 矩阵。如果 word1[i-1] 等于 word2[j-1]，表示这两个字符相同，则不需要任何操作，dp[i][j] 等于 dp[i-1][j-1]。否则，算法需要在 word1 的前 i-1 个字符中添加、删除或替换一个字符，使之变为 word2 的前 j 个字符。算法选择最小的操作次数，将 dp[i][j] 设为 dp[i-1][j]、dp[i][j-1] 和 dp[i-1][j-1] 中的最小值加一。

最后，算法返回 word1 的长度加上 word2 的长度减去 2 乘以 dp[word1.size()][word2.size()]，因为每个匹配的字符只需要计算一次，而不是两次。

1.动态规划

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

72 编辑距离

思路：算法的核心是状态转移方程，对于word1的第i个字符和word2的第j个字符有两种情况：

word1[i-1] == word2[j-1]，即两个字符相同，此时编辑距离不需要进行任何操作，所以dp[i][j] = dp[i-1][j-1]。
word1[i-1] != word2[j-1]，即两个字符不同，此时可以有三种操作：
替换操作：将word1[i-1]替换成word2[j-1]，此时编辑距离为dp[i-1][j-1]+1。
插入操作：在word1[i-1]后面插入word2[j-1]，此时编辑距离为dp[i][j-1]+1。
删除操作：删除word1[i-1]，此时编辑距离为dp[i-1][j]+1。
由于需要取最小值，所以状态转移方程为dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1。

初始化时，当i=0或j=0时，dp[i][j]为i或j，因为此时需要进行的操作次数就是i或j。

最终结果为dp[word1.size()][word2.size()]，即word1和word2之间的最小编辑距离。

1.动态规划

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int> (word2.size() + 1, 0));
        for(int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        for(int j = 0; j <= word2.size(); j++) dp[0][j] = j;
        for(int i = 1; i <= word1.size(); i++){
            for(int j = 1; j <= word2.size(); 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], dp[i - 1][j], dp[i][j - 1]}) + 1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};