本文共 2512 字，大约阅读时间需要 8 分钟。

（2）S[i-1] 即表示 S 的第 i-1 个字符。

使用动态规划来处理，则有 dp[i][j] 代表 S(0, i-1) 与 T(0, j-1) 对应的解。

对于 dp[i][j] 有：

1. 当 S[i-1] 与 T[j-1] 不相等时，则 S 的第 i-1 个字符肯定是要删除的，删除了 S 的第 i-1 个字符，就等价于求 S(0, i-2) 与 T(0, j-1) 的解，因此 dp[i][j] 就等价于 dp[i-1][j]。

   也可以反过来想，对于 T(j-1) ，当 S[i-1] 与 T[j-1] 不相等时，对于 S 的前 i-1 个字符(即 S(0, i-2))，再加上第 i-1 个字符，是不会影响到关于 T(j-1) 的结果的。

2. 当 S[i-1] 与 T[j-1] 相等 时，S 的第 i-1 个字符也是要删除的，但是当其删除时，就会有两种情况：

   抵消掉 T[j-1]（即抵消掉 T 的第 j-1 个字符，则剩下 T 的前 (j-1) 个字符，此时最后一个字符变为第 T[j-2] 个了），此时就对应于 dp[i-1][j-1]；

   或者不抵消（即 T 的第 j-1 个字符还在，则剩下的依然是 T 的前 j 个字符），此时对应于 dp[i-1][j]。

   此时 dp[i][j] 为两种情况的和，即 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。

public int numDistinct(String s, String t) {
       if (s == null || s.length() == 0) {
           return 0;    }    if (t == null || t.length() == 0) {
           return 1;    }        int sLen = s.length();    int tLen = t.length();    // 注意数组空间为 [sLen + 1][tLen + 1]    int[][] dp = new int[sLen + 1][tLen + 1];		// 初始值赋值    for (int i = 0; i <= sLen; i++) {
           dp[i][0] = 1;    }        // 最终要求得 dp[sLen][tLen]    for (int i = 1; i <= sLen; i++) {
           for (int j = 1; j <= tLen; j++) {
               if (s.charAt(i - 1) == t.charAt(j - 1)) {
                   dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];            } else {
                   dp[i][j] = dp[i - 1][j];            }        }    }    return dp[sLen][tLen];}

注意，对于 dp[i][0]，即 T 的字串长度为 0 的时候，有 dp[i][0] 为 1，即空字符串为 S 的子串只有一种可能，那就是删除 S 的所有字符。

而对于 dp[0][j] 不包括 dp[0][0]（因为它属于 dp[i][0] 对应的情形 ），即 S 为空字符串，此时不管 T 多长，都无法通过删除 S 中的字符来变成 T，因此 dp[0][j] 为 0。

上述实现的空间复杂度为 O(sLen*tLen)

空间复杂度还可以优化，即使用一纬的辅助数组，此时重点就是对于 dp[i-1][j-1] 状态的保存，因为它在遍历的时候会被 dp[i][j-1] 给覆盖。

此时，就可以用一个临时变量，来保存被覆盖之前的 dp[i-1][j-1] 状态。

public int numDistinct(String s, String t) {
       if (s == null || s.length() == 0) {
           return 0;    }    if (t == null || t.length() == 0) {
           return 1;    }    int sLen = s.length();    int tLen = t.length();    // 使用一纬数组，此时 dp[j] 表示 t 的前 j 个字符    int[] dp = new int[tLen + 1];    dp[0] = 1;    for (int i = 1; i <= sLen ; i++) {
           int pre = dp[0];        dp[0] = 1;        for (int j = 1; j <= tLen; j++) {
               // 用临时状态保存更新前的 dp[j]，此时为 dp[i-1][j-1] 对应的状态            int tmp = dp[j];            if (s.charAt(i-1) == t.charAt(j-1)) {
                   dp[j] = pre + tmp;            } else {
                   dp[j] = tmp;            }            // 将更新前的 dp[i] 赋值给 pre，用于遍历下一个元素            pre = tmp;        }    }    return dp[tLen];}

转载地址：http://drerj.baihongyu.com/