sequence alignment 典型的問(wèn)題，只是mismatch和gap的cost都是1的簡(jiǎn)化版。如果單純的dp這道題可能不值hard的難度。關(guān)鍵是如果把O(mn)的space變成O(m+n); 再高級(jí)一點(diǎn)的improvement是加上divide and conquer.
參考：Algorithm Design，chapter 6

// 最基本的DP思想：時(shí)間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) 重點(diǎ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];
    }
}