Edit Distance

动规 就是递推。。。比较难想 然后数组长度设置比字符串长度多一，并做一定的初始化，都是为了方便边界条件的设置。。。。

public class Solution {
    public int minDistance(String word1, String word2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int length1 = word1.length();
        int length2 = word2.length();
        int[][] distance = new int[length1+1][length2+1];
        for (int i = 0; i <= length1; i++)
            distance[i][0] = i;
        for (int i = 0; i <= length2; i++)
            distance[0][i] = i;
        for (int i = 1; i <= length1; ++i)
            for (int j = 1; j <= length2; ++j){
                int add = 1 + distance[i-1][j];
                int minus = 1 + distance[i][j-1];
                int replace = (word1.charAt(i-1) == word2.charAt(j-1) ? 0 : 1) + distance[i-1][j-1];
                distance[i][j] = Math.min(Math.min(add, minus), replace);
            }
        return distance[length1][length2];
    }
}