https://leetcode.com/problems/edit-distance/description/

參考 CodeGanker:

我們維護的變量res[i][j]表示的是word1的前i個字符和word2的前j個字符編輯的最少操作數(shù)是多少建椰。假設我們擁有res[i][j]前的所有歷史信息元莫，看看如何在常量時間內(nèi)得到當前的res[i][j]殴胧，我們討論兩種情況：
1）如果word1[i-1]=word2[j-1]，也就是當前兩個字符相同，也就是不需要編輯旷太，那么很容易得到res[i][j]=res[i-1][j-1]倔监，因為新加入的字符不用編輯；
2）如果word1[i-1]!=word2[j-1]刹孔，那么我們就考慮三種操作:
2.1) 如果是刪除word1[i - 1]啡省，那么res[i][j]=res[i-1][j]+1娜睛，也就是取word1前i-1個字符和word2前j個字符的最好結果，然后一個刪除操作卦睹；
2.2) 如果是刪除word2[j - 1]畦戒，那么res[i][j]=res[i][j-1]+1，道理同上面一種操作结序；
2.3) 如果是替換操作障斋，那么類似于上面第一種情況，但是要加一個替換操作（因為word1[i-1]和word2[j-1]不相等）徐鹤，所以遞推式是res[i][j]=res[i-1][j-1]+1垃环。

上面列舉的情況包含了所有可能性。

兩點思考：

• 刪除和插入操作對應的操作數(shù)是一樣的返敬；"" => "abc" 進行插入操作 同 “abc” => "" 進行刪除操作遂庄，所需的操作數(shù)是一致的；
• 刪除操作應該是更容易維護和進行推導運算的劲赠。因為刪除 word[index] 處的 char涛目，繼續(xù)向下進行 word[greaterThanIndex] 的 chars 可以繼續(xù)進行；相反凛澎，對word index 處插入新的char霹肝，會使原來的 char 后移，word 位數(shù)增加塑煎，該 char 仍須繼續(xù)被計算沫换；

class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word1.length() == 0) {
            return (word2 == null) ? 0 : word2.length();
        }
        if (word2 == null || word2.length() == 0) {
            return (word1 == null) ? 0 : word1.length();
        }
        
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        
        for (int i = 1; i <= len1; i++) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= len2; j++) {
                char c2 = word2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int replace = dp[i - 1][j - 1] + 1; // replace c1 to c2 in word1
                    int delete = dp[i - 1][j] + 1;      // delete c1 in word1 at (i - 1)
                    int insert = dp[i][j - 1] + 1;      // delete c2 in word2 at (j - 1)
                    dp[i][j] = Math.min(Math.min(replace, delete), insert);
                }
            }
        }
        return dp[len1][len2];
    }
}

From 九章：

Edit Distance
state: f[i][j]a的前i個字符“配上”b的前j個字符 最少要用幾次編輯使得他們相等
function:
f[i][j] = MIN(f[i-1][j-1], f[i-1][j]+1, f[i][j-1]+1) // a[i] == b [j]
= MIN(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 // a[i] != b[j] intialize: f[i][0] = i, f[0][j] = j
answer: f[a.length()][b.length()]