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

問(wèn)題是把word1變?yōu)閣ord2最少需要多少步操作，每一步操作你可以增加、刪除或替換一個(gè)字符。
這是一道典型的雙序列動(dòng)態(tài)規(guī)劃問(wèn)題。
1、確定狀態(tài)。f[i][j]表示把word1的0到i-1變化成word2的0到j(luò)-1最少需要的操作步數(shù)。
2、狀態(tài)轉(zhuǎn)移方程。當(dāng)word1.charAt(i-1)與word2.charAt(j-1)相等時(shí)，顯然這兩個(gè)字符無(wú)需變換，所以f[i][j] = f[i-1][j-1]；當(dāng)不相等時(shí)，f[i][j]可以由f[i-1][j]變化來(lái)，此時(shí)相當(dāng)于刪除了word1的第i-1個(gè)字符，也可以由f[i][j-1]變化而來(lái)，相當(dāng)于word1增加了word2的第j-1個(gè)字符，還可以由f[i-1][j-1]變化來(lái)，相當(dāng)于把word1的i-1替換為word2的j-1，所以在不相等時(shí)，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，因?yàn)閺?個(gè)字符變到i個(gè)字符，只需要增加i個(gè)相同字符即可。

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];
}