72. Edit Distance

sequence alignment 典型的问题，只是mismatch和gap的cost都是1的简化版。如果单纯的dp这道题可能不值hard的难度。关键是如果把O(mn)的space变成O(m+n); 再高级一点的improvement是加上divide and conquer.
参考：Algorithm Design，chapter 6

// 最基本的DP思想：时间O(mn)，空间O(mn)
public class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length(), n2 = word2.length();
        int dp[][] = new int[n1+1][n2+1];
        dp[0][0] = 0;
        // w1 is empty:
        for(int j=1; j<=n2; j++)
            dp[0][j] = j;
        // w2 is empty:
        for(int i=1; i<=n1; i++)
            dp[i][0] = i;        
        // fill the table:
        for(int i=1; i<=n1; i++) {
            for(int j=1; j<=n2; j++) {
                if(word1.charAt(i-1) == word2.charAt(j-1))  dp[i][j] = dp[i-1][j-1];
                else    dp[i][j] = Math.min(Math.min(1+dp[i-1][j-1],1+dp[i-1][j]), 1+dp[i][j-1]);
            }
        }
        return dp[n1][n2];
    }
}

//空间的improvement：空间O(m+n) 重点在把DP table的n列变成两列，previous iteration的值和 current iteration的值。

public class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length(), n2 = word2.length();
        int dp[][] = new int[n1+1][2];
        // p is empty:
        for(int i = 0; i<=n1; i++) {
            dp[i][0] = i;
        }
        // s is empty:
        for(int j = 1; j<=n2; j++) {
            dp[0][1] = j;
            for(int i=1; i<=n1; i++) {
                if(word1.charAt(i-1) == word2.charAt(j-1))
                    dp[i][1] = dp[i-1][0];
                else 
                    dp[i][1] = Math.min(Math.min(1+dp[i-1][0], 1+dp[i-1][1]), 1+dp[i][0]);
            }
            for(int i=0; i<=n1; i++) {
                dp[i][0] = dp[i][1];
            }
        }
        return dp[n1][0];
    }
}