算法细节系列（14）：动态规划之字符串处理

    public boolean isSubsequence(String s, String t){

        if (s.isEmpty()) return true;
        int n = s.length();
        boolean[] isSeq = new boolean[n];

        int index = 0;
        for (int i = 0; i < t.length(); i++){
            if (s.charAt(index) == t.charAt(i)){
                isSeq[index++] = true;
                if (isSeq[n-1]) return true;
            }
        }
        return isSeq[n-1];
    }

//dp[j][i] 表示在区间[j,i]之间的最长回文，可断
s[j] == s[i]: dp[j][i] = dp[j+1][i-1] + 2;
//没有最新的回文生成，所以沿用旧的回文长度
s[j] != s[i]: dp[j][i] = Math.max(dp[j+1][i],dp[j][i-1]);

public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        char[] c = s.toCharArray();
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
            for (int j = i-1; j >= 0; j--) {
                if (c[j] == c[i]) {
                    dp[j][i] = dp[j + 1][i - 1] + 2;
                } else {
                    dp[j][i] = Math.max(dp[j+1][i], dp[j][i-1]);
                }
            }
        }
        return dp[0][n-1];
    }

dp[i][j] : 表示word1[0,i)和word2[0,j)的最短编辑距离
如：
dp[1][0] = 1, "a"," "
dp[1][1] = ?, "a","a" 相等，？ = 0，"a","b" 不相等， ？ = 1

初始化：（字符串为空串的情况下，最短编辑距离等于字符串长度）
dp[i][0] = i;
dp[0][j] = j;

递推式：
dp[i][j] = dp[i-1][j-1];  if word1[i] == word2[j];
dp[i][j] = min(dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]) + 1; if word1[i] != word2[j];

举个简单的例子说明它们的含义：（word1不去操作，所有操作在word2上进行）
word1 : "a"
word2 : "ab"
dp[0][0] = 0; " " == " "
dp[0][1] = 1; edit -> "&a", "&b"
dp[0][2] = 2; edit -> "&&a", "&&"
dp[1][1] = dp[0][0] = 0; "a" == "a", no edit
dp[1][2] = ?; "a" != "b"
存在三种情况：
a. dp[1][2] = dp[0][1] = 2; "&a","&b" edit -> "&a","&a"
我们已知道了dp[0][1]表示为"&a","&b",所以只能进行替换操作。
即：dp[i][j] = dp[i-1][j-1]
dp[i-1][j-1]表示了最短编辑距离，也可以表示成两字符串经过编辑后已然相等，而此时为了能够更新到dp[i][j],只能对word2的第j个字符做替换操作。

b. dp[1][2] = dp[1][1] = 1; "a","ab" edit -> "a","a"
即：dp[i][j] = dp[i][j-1]
显然，dp[1][1] = 0,没有操作。而此时为了能够更新到dp[i][j]，让两字符串相等，只能删除word2的第j个字符。

c. dp[1][2] = dp[0][2] = 3; "&&a","&&" edit -> "&&a","&&a"
即：dp[i][j] = dp[i-1][j];
同理，dp[0][2] = 2, 说明了word2 = "&&",而为了能够更新到dp[i][j],只能添加到第j个字符后。

最后在这三种操作中，取最小的即可。

    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        int[][] cost = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++)
            cost[i][0] = i;
        for (int i = 1; i <= n; i++)
            cost[0][i] = i;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (word1.charAt(i) == word2.charAt(j))
                    cost[i + 1][j + 1] = cost[i][j];
                else {
                    int a = cost[i][j];
                    int b = cost[i][j + 1];
                    int c = cost[i + 1][j];
                    cost[i + 1][j + 1] = a < b ? (a < c ? a : c) : (b < c ? b : c);
                    cost[i + 1][j + 1]++;
                }
            }
        }
        return cost[m][n];
    }