https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html

1.本题一开始的想法就是求出两个字符串的最长公共子序列，这样最后两个字符串长度减去二倍的最长公共子序列即可，等二刷的时候再来挑战，本题使用正常的dp数组含义为dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。还是当两个数相等的时候，直接取dp[i - 1][j - 1]即可当两个数不相等的时候就是删除元素的操作，两个字符串都可以删，所以选择一个最小的操作数即可。在这里我的疑惑是为什么是取删除word1和word2的最小值而不是将两个数相加，是因为在操作其中一个字符串的时候在这个状态中已经存储删去另一个字符串的操作数了。例如
word1 = “abc”, word2 = “abcd”，从 abc 到 abcd，我们只需要删除一个字符 d，并不需要删除全部。
每次删除操作是独立的，只需要一次操作即可。取最小值的逻辑表示我们总是选择当前最优解，而不是盲目叠加所有可能的操作次数。

CPP

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, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};