72.编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符，删除一个字符，替换一个字符。

输入：word1 = "horse", word2 = "ros" 输出：3 解释：horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

1.一刷动规

首先题目说了可以对word1或者word2操作，只要变成相同的就可以，没有要求变成两个字符串的公共子串，那么删除操作和填入操作是等价的，对word1删除等价于对word2添加。

• 不考虑删除实际上只有三种操作：①在word1添加②在word2添加③替换word1或者word2字符。这里说明一下，③中把1中的字符替换成2的字符和把2的字符替换成1的字符是等价的；而①和②是不等价的，比如"ab"和"a"你只能在word2添加字符b而不能在word1添加。
• dp[i][j]表示前word1前i个字符和word2前j个字符的编程距离，如果word1[i]不等于word2[j]，那么就可以通过word1或者word2尾元素进行上述三种操作变成相同的，因此状态转移方程如下：dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)。 需要注意的是，如果word1[i]等于word2[j],那么相同元素就不需要动了，状态转移到字符串前移一个元素dp[i][j]=dp[i-1][j-1]。这种方法对于需要在头元素进行操作的情况也是适用的，举个例子"aaabcdefggg"和"bcdef",计算时dp[i-1][j]会前溯到dp[i-3][j]把不等的去掉，实际上dp[i-1][j]的结果就是已经考虑了把word1尾指针前移的最优解。这种dp写法是基于对尾元素进行操作的，也可以写成对首元素操作，那样的话遍历方向要从字符串后往前。

2.二刷

分析：注意dp[i][0]初始化的操作，需要直接把前i个字符串的长度作为操作数，而不能设置为dp[i-1][0]。例子"aaafbbf"和"f"

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp=new int[word1.length()][word2.length()];
        int res=0;
        if(word1.length()==0||word2.length()==0) return Math.max(word1.length(),word2.length());
        dp[0][0]=word1.charAt(0)==word2.charAt(0)?0:1;
        for(int i=1;i<word1.length();i++){
            dp[i][0]=dp[i-1][0]+1;
            //细节：直接将前i个字符串的长度i赋给当前dp的结果
            if(word1.charAt(i)==word2.charAt(0))dp[i][0]=Math.min(dp[i][0],i);
        }
        for(int i=1;i<word2.length();i++){
            dp[0][i]=dp[0][i-1]+1;
            if(word1.charAt(0)==word2.charAt(i))dp[0][i]=Math.min(dp[0][i],i);
        }
        for(int i=1;i<word1.length();i++){
             for(int j=1;j<word2.length();j++){
                //上与左
                dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j])+1;
                //左上
                dp[i][j]=Math.min(dp[i-1][j-1]+1,dp[i][j]);
                if(word1.charAt(i)==word2.charAt(j)){
                    dp[i][j]=Math.min(dp[i][j],dp[i-1][j-1]);
                }
            }
        }
        return dp[word1.length()-1][word2.length()-1];
    }
}