求解编辑距离（Edit Distance）

题目链接：https://leetcode.com/problems/edit-distance/description/。
字符串相关的算法题的求解，很多需要用到动态规划思想。动态规划本质以空间换时间，记录发生过的状态，用于后面状态的处理，避免重复计算。难点在于状态转换规律的总结。
回到编辑距离的问题上来。定义二维矩阵dp，dp[i][j]表示长度为i和j的两个字符串的编辑距离。接下来，我们探讨dp[i][j]与dp[i-1][j-1]的递推关系，假定第一个字符串（word1）的末字符为“x”，第二个字符串（word2）的末字符为“y”，如下图：

Edit Distance

1. 如果x == y，dp[i][j] == dp[i-1][j-1];
2. 如果x != y，word1字符串插入y，则dp[i][j] = dp[i][j-1] + 1;
3. 如果x != y，word1字符串删除x，则dp[i][j] = dp[i-1][j] + 1;
4. 如果x != y，word1字符串替换x为y，则dp[i][j] = dp[i-1][j-1] + 1;
5. 所以，当x !=y，dp[i][j]为这三种情形的最小值。
   还有一点，dp二维数组的初始化：
   dp[i][0] = i，dp[0][j] = j。
   Accept代码如下:

class Solution {
    public int minDistance(String word1, String word2) {
        // +1是为了从len=0的字符串算起
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        // dp二维数组的初始化
        dp[0][0] = 0;
        for (int i=1; i<word1.length()+1; i++)
        {
            dp[i][0] = i;
        }
        for (int i=1; i<word2.length()+1; i++)
        {
            dp[0][i] = i;
        }
       // dp的关系递推
        for (int i=1; i<word1.length()+1; i++)
            for(int j=1; j<word2.length()+1; j++)
            {
                if(word1.charAt(i-1) == word2.charAt(j-1))
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                }
            }
        return dp[word1.length()][word2.length()];
    }
}