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
问题是把word1变为word2最少需要多少步操作，每一步操作你可以增加、删除或替换一个字符。
这是一道典型的双序列动态规划问题。
1、确定状态。f[i][j]表示把word1的0到i-1变化成word2的0到j-1最少需要的操作步数。
2、状态转移方程。当word1.charAt(i-1)与word2.charAt(j-1)相等时，显然这两个字符无需变换，所以f[i][j] = f[i-1][j-1]；当不相等时，f[i][j]可以由f[i-1][j]变化来，此时相当于删除了word1的第i-1个字符，也可以由f[i][j-1]变化而来，相当于word1增加了word2的第j-1个字符，还可以由f[i-1][j-1]变化来，相当于把word1的i-1替换为word2的j-1，所以在不相等时，f[i][j]等于f[i-1][j-1]、f[i-1][j]、f[i][j-1]三者中最小值再加1。
3、初始化。f[0][j]和f[i][0]的值都等于j和i，因为从0个字符变到i个字符，只需要增加i个相同字符即可。
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return 0;
}
int l1 = word1.length();
int l2 = word2.length();
int[][] dp = new int[l1 + 1][l2 + 1];
dp[0][0] = 0;
for (int i = 1; i <= l1; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= l2; i++) {
dp[0][i] = i;
}
for (int j = 1; j <= l2; j++) {
for (int i = 1; i <= l1; i++) {
if (word1.charAt(i-1) == word2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
}
}
}
return dp[l1][l2];
}