ref: https://discuss.leetcode.com/topic/3136/my-o-mn-time-and-o-n-space-solution-using-dp-with-explanation/2

如果用dp[i][j]表示word1里[0,i]长的子串和word2[0,j]的最小编辑距离，那么状态转移方程应该这样构成：

dp[i][j] = dp[i-1][j-1], if word1[i] == word2[j]dp[i][j] = max{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} + 1, otherwise

如果word1[i] == word2[j]的时候不需要解释，

如果不相等的时候可能有三种操作，使两个字符串对齐：

　　1. 替换字母：把word1[i] 替换成word2[j]，那么是dp[i-1][j-1]+1

　　2. 在Word1[i]后面强行插入一个word2[j]. 所以可能是dp[i][j-1]

　　3. 直接把word1[i]删了，dp[i-1][j]

 

所以用二维矩阵表示很容易：

 

1 public int minDistance(String word1, String word2) { 2     int len1 = word1.length(); 3     int len2 = word2.length(); 4      5     //distance[i][j] is the distance converse word1(1~ith) to word2(1~jth) 6     int[][] distance = new int[len1 + 1][len2 + 1];  7     for (int j = 0; j <= len2; j++) 8         {distance[0][j] = j;} //delete all characters in word2 9     for (int i = 0; i <= len1; i++)10         {distance[i][0] = i;}11 12     for (int i = 1; i <= len1; i++) {13         for (int j = 1; j <= len2; j++) {14             if (word1.charAt(i - 1) == word2.charAt(j - 1)) { //ith & jth15                 distance[i][j] = distance[i - 1][j - 1];16             } else {17                 distance[i][j] = Math.min(Math.min(distance[i][j - 1], distance[i - 1][j]), distance[i - 1][j - 1]) + 1;18             }19         }20     }21     return distance[len1][len2];        22 }

但是，可以像uniquePath一样把二维压成一维

pre表示上同一行前一列的值，f[j-1]表示f[i-1][j-1]（因为pre没有更新进去），f[j]表示同一列上一行

 

1     public int minDistance(String word1, String word2) { 2         if(word1 == null || word2 == null) { 3             return -1; 4         } 5         int len1 = word1.length(); 6         int len2 = word2.length(); 7         int[] distance = new int[len2 + 1]; 8         for(int i = 0; i <= len2; i++) { 9             distance[i] = i;10         }11         for(int i = 1; i <= len1; i++) {12             int pre = i;13             for(int j = 1; j <= len2; j++) {14                 int cur = 0;15                 if(word1.charAt(i - 1) == word2.charAt(j - 1)) {16                     cur = distance[j - 1];17                 } else {18                     cur = Math.min(pre, Math.min(distance[j], distance[j - 1])) + 1;19                 }20                 distance[j - 1] = pre;21                 pre = cur;22             }23             distance[len2] = pre;24         }25         return distance[len2];26     }