leetcode 72.编辑距离

这道题其实也是经典的DP问题了，也就是最长公共子序列那一类问题延续过来的。

思路：首先我们看到，有三种状态，也就是增加，删除，和替换。如果操作里面没有替换这一项，那么就和最长公共子序列是一样的。不过还是有点不同的地方。

第一，最长公共子序列的要求是求出来最长的子序列，也就是所有公有元素。但是这里的要求是需要你修改出来所给字符串。表面上看着不一样，其实就可以这样的转化过来：怎样从所给字符word1变成word2转变成找出最长子序列为word2需要进行的最少操作数。

第二，这里的要求不一样，是最少的操作数，并不是什么最长，因此需要用到min，而不是max。

不同也就这么几点，接下来就是dp的递推问题了：

我们想，如果我们遍历的两个字符串的元素当前刚好相同会怎么办？我们不会将它加上，因为这又不是拼接字符串，为啥要加呢？答案是不操作，直接继承dp[i-1][j-1]的结果。既然是相同，我们就没必要做出来任何改变了，这样才能保证编辑的次数最少。

那么，关键是在不相同的时候要怎么办？这里给了我们三个状态：替换，删除，增加。我们这几个状态我们怎么表示才好呢？

删除，我们需要删除word1，这个时候就只剩下了dp[i-1][j]，但是操作数需要+1，也就是dp[i-1][j]+1;添加，其实我们可以这样理解，在word1上添加一个元素，和在word2上删除一个元素是等价的。也就是dp[i][j]=dp[i][j-1]+1，我们的目的是一样的，都是想让word1修改当前位置的字符与当前word2位置的字符尽可能的相等，添加一个元素让它相同，和删除word2的这个元素解决这个位置的问题，是等价的，同时操作数都是+1，也是一样的。

最后，就是替换操作了，既然我们在当前位置进行替换word1的元素，那么这个操作数也就是+1了，但是它的状态如何呢？回顾我们word1[i]==word2[j]操作时状态是怎么变化的？

是dp[i-1][j-1]。而我们此时让这个比较的位置相同了，只不过我们做了修改操作，所以：

dp[i][j]=dp[i-1][j-1]+1这个状态方程就出来了。

上代码：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n=word1.size();
        int m=word2.size();
        vector<vector<int>>dp(550,(vector<int>(550,0)));
        for(int i=1;i<=n;i++)
        dp[i][0]=i;
        for(int i=1;i<=m;i++)
        dp[0][i]=i;
        if(n==0||m==0)
        return n+m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(word1[i-1]!=word2[j-1])
                dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                else
                dp[i][j]=dp[i-1][j-1];
            }
        }
        return dp[n][m];
    }
};