通过Edit Distance问题理解动态规划算法

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

public int minDistance(String word1, String word2) {
if (word1 == null && word2 == null)
return 0;
if (word1 == null || word1.isEmpty())
return word2.length();
if (word2 == null || word2.isEmpty())
return word1.length();
int m = word1.length();
int n = word2.length();

    // Cost[i][j]表示words1.substr(0, i)到 words2.substr(0, j) 的最短编辑距离
    int[][] Cost= new int[m+1][n+1];
    // 初始化边界情况
    for (int i = 0; i <= m; ++i) 
     Cost[i][0] = i;
    for (int j = 0; j <= n; ++j) 
     Cost[0][j] = j;
    
    // 由A[0...i]到B[0...j]的最短距离分为三种情况
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
         int insertBoth = Cost[i-1][j-1] + replaceCost(word1, word2,0,0);
         int insertA = Cost[i-1][j] + 1;
         int insertB = Cost[i][j-1] + 1;
            Cost[i][j] = Math.min(Math.min(insertA, insertB), insertBoth);
        }
    }

    return Cost[m][n];
  }
private int replaceCost(String word1, String word2, int i1, int i2) {
return word1.charAt(i1) == word2.charAt(i2) ? 0 : 1;
}