子序列——一个字符串有多少个指定的子序列（九）

LeetCode_115_DistinctSubsequences

题目分析：

  Ø r a b b b i t
Ø 1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
dp[i][j] = dp[i][j - 1] + 
(t.charAt(i - 1) == s.charAt(j - 1) ? dp[i - 1][j - 1] : 0);
字符相等等于左方加左上方 不然等于左方
什么意思？
横向扫描到dp[i][j]了

一个t[j - 1]进来问，我新增的值是否和s当前的最后值s[i - 1]相等
不相等：
由于t新增进来的只可能当最后一个值，所以如果不等，那么完全不起任何作用，
就和没有t[j - 1]的时候情况一样，也就是等于左方值dp[i][j - 1]。
相等：
除了当没有我的情况左方外，我还能作为“新的”s尾巴，
所以把s中没有s[i - 1]情况下的所有情况也算上,也就是左上方值dp[i - 1][j - 1]。
初始项：
dp[0][0] = 1，空串可以配空串。
然后第一行都是1，任何串都算一个有一个空串的子序列。
第一列剩下都是0，空串没有任何非空串子序列。

解法：

public static int numDistinct(String s, String t) {
    int [][]dp = new int[t.length() + 1][s.length() + 1];
    for (int i = 0; i <= s.length(); ++i) dp[0][i] = 1;
    for (int i = 1; i <= t.length(); ++i) dp[i][0] = 0;
    for (int i = 1; i <= t.length(); ++i) {
        for (int j = 1; j <= s.length(); ++j) {
            dp[i][j] = dp[i][j - 1] + (t.charAt(i - 1) == s.charAt(j - 1) ? dp[i - 1][j - 1] : 0);
        }
    }
    return dp[t.length()][s.length()];
}