学步园

题目：

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character

b) Delete a character

c) Replace a character

思路：

关于两字符串的比较的DP问题，思路往往是从两个字符串的开头进行比较，从而建立比较的前置基础。

首先定义一个函数edit（i，j），表示第一个串从0到i和第二个串从0到j的这两个子串进行比较。

那么，edit（0,0）就表示两个串儿的首字母进行比较。而edit（0,1）依赖于edit（0,0），edit（0,i）=min( edit(0,i-1)+1, i+（w1[0]==w2[i]?0:1）);依次类推。解释一下该式，该式仅建立在边界上，即第一个串的第一个字母对另外一整个串的情况：edit（0,i-1）+1意味着承认了0到i-1的结果，则第i个肯定是多出来的。i+（w1[0]==w2[i]?0:1）表示，不承认之前那个结果，而将这个字母与最后一个字母进行匹配计算，这时，前面i个就都是不匹配的了。因此，比较这两种情况，得到一种最小值，即为边界。

第一列的结果也以此类推，这样第一行和第一列的子结果就都有了。

接下来，看中间的其他结果edit（i，j），他的结果来自于3种可能，一种是edit（i-1，j）+1，即认为在前一个状态的基础上，第一个子串多了一位；

一种是edit(i,j-1)+1,即认为在前一个状态的基础上，第二个子串多了一位；第三种为edit(i-1,j-1)+(w1[i]==w2[j]?0:1),即在前一个状态基础上，比较各自串末尾的两个字符，如果相等，则结果等于edit（i-1，j-1）；如果不等，则加1.

最终，edit（i，j）使用以上三种情况产生的三个结果中最小的一个值即可。

以下为举例演示，其中我们使用二维数组w[i][j]表示edit（i，j）的状态值。

对于这两个字符串，首先计算边缘情况，即edit（0，i）和edit（i，0），如下：

然后，依次按照行的顺序计算edit（i，j）的值。之所以能够按照这个顺序进行计算，是因为每一个edit（i，j）的结果都依赖于edit（i-1，j）和edit(i,j-1)以及edit(i-1,j-1)的值，在空间上看，也就是w[i][j]上方、左方 和左上方的元素。举例来看：

edit(1,1)需要edit（0,1）、edit（1,0）和edit（0,0）。

根据上面的递推公式，得到edit（1，1）=1；

依次类推，最终结果一定是edit（5,7），空间上看就是w[5][7].

AC代码：

public class Edit_Distance {
    private int min(int a,int b,int c){
        int first = Math.min(a,b);
        return Math.min(first,c);
    }
    public int minDistance(String word1, String word2) {

        int m = word1.length();
        int n = word2.length();
        if(m==0)
            return n;
        if(n==0)
            return m;
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        int[][] w = new int[m][n];

        for(int i=0;i<n;i++){
            if(i>0){
                w[0][i]= Math.min(w[0][i-1]+1,i+(w1[0]==w2[i]?0:1));
            }
            else{
                w[0][i]=w1[0]==w2[i]?0:1;
            }
        }

        for(int i=0;i<m;i++){
            if(i>0){
                w[i][0] = Math.min(w[i-1][0]+1,i+(w1[i]==w2[0]?0:1));
            }
            else{
                w[i][0] = w1[i]==w2[0]?0:1;
            }
        }


        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                w[i][j]=min(w[i-1][j]+1,w[i][j-1]+1,w[i-1][j-1]+(w1[i]==w2[j]?0:1));
            }
        }
        return w[m-1][n-1];
    }
}