leetcode 72. 编辑距离

思路：

dp[i][j]表示以word1[i]结尾的字符串，变为以word2[j]结尾的字符，需要的最少编辑次数。

若word1[i]==word2[j] ，那么不需要任何操作dp[i][j]=dp[i-1][j-1]

若不等，则有三种方法

1. 删除一个字符, 即dp[i][j]=dp[i-1][j] +1（意思是，删除掉word1[i]以后，两个字符串相同，那么也就等价于word1[i-1]与word2[j]）

2. 替换。这个比较容易理解，替换一个，那么前面的word1[i-1]和word2[j-1]一定相同。dp[i][j]=dp[i-1][j-1]+1

3. 插入，这个比较难理解。在word1[i]后面插入一个字符，其实等价于把word[j]删除。即dp[i][j]=dp[i][j-1]。也就是word1[i]之前的字符，要和word2[j-1]以前的字符相同。

这三种方法取最小值即可。

写代码的时候，要注意初始化。

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size();
        int n2=word2.size();
        int dp[n1+3][n2+3];
        memset(dp,0,sizeof(dp));
        for(int j=1;j<=n2;j++)
        {
            dp[0][j]=j;
        }
        for(int i=1;i<=n1;i++)
        {
            dp[i][0]=i;
        }
        for(int i=1;i<=n1;i++)
        {
            for(int j=1;j<=n2;j++)
            {
                if(word2[j-1]==word1[i-1])
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                else
                {
                    dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
                }
            }
        }
        return dp[n1][n2];
    }
};