https://leetcode.com/problems/edit-distance/
給定兩個字符串word1,word2全蝶，求從word1變到word2所需要的最小步驟德迹，沒次變化只能是增刪改其中一個字母
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

• 例子：
  s1="bbc" ,s2="abcd"
  ||?|a|b|c|d|
  |---|---|---|---|---|---|
  |? |0|1|2|3|4|
  |b |1|1|1|2|3|
  |b |2|2|1|2|3|
  |c |3|3|2|1|2|
  狀態(tài)轉移方程

if(word1(i-1) == word2(j-1)){
    dp[i][j] = dp[i-1][j-1];
}else{
    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
}

• 代碼

public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        int[][] dp = new int[m + 1][n + 1];

        //翻譯翻譯
        //從word1轉為空的情況芽卿，只能全做刪除
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        //翻譯翻譯
        //從空轉為word2的情況，只能一個一個加
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                //翻譯翻譯
                //如果word1的當前字符等于word2的當前字符胳搞，那他們的轉換次數與上一個字符的次數相等
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //dp[i - 1][j - 1] + 1 代表修改
                    //dp[i - 1][j] + 1 代表刪除
                    //dp[i][j-1] + 1 代表插入
                    //細細的品味下
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }

        return dp[m][n];
    }