算法训练第五十六天

总结：今日是编辑距离问题的结束，对编辑距离问题的总结是要抓住dp的定义以及如何推出dp数组来抓住问题核心，比如经典题目编辑距离：dp数组的定义是dp[j][j]是以i - 1为尾的word1和j - 1为尾的word2的最少改变次数能使两个字符串相等，dp[i][j]则可由以下几种情况推出：当word1[i - 1]和word2[j - 1]相等时，则dp等于dp[i - 1][j - 1]，不相等时：（以下摘抄自代码随想录）

• 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。

即 dp[i][j] = dp[i - 1][j] + 1;

• 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。

即 dp[i][j] = dp[i][j - 1] + 1;

这里有同学发现了，怎么都是删除元素，添加元素去哪了。

word2添加一个元素，相当于word1删除一个元素，例如 word1 = "ad" ，word2 = "a"，word1删除元素'd' 和 word2添加一个元素'd'，变成word1="a", word2="ad"， 最终的操作数是一样！

代码：

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

583. 两个字符串的删除操作 - 力扣（LeetCode）

总结：距离问题的前置题目，为距离问题做铺垫，注意此题当word1[i - 1]和word2[j - 1]不相等时dp数组的求法与距离问题不同。

代码：

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