Distinct Subsequences(Hard)
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
解题思路
我们需要一个二维数组dp(i)(j)来记录长度为i的字串在长度为j的母串中出现的次数，这里长度都是从头算起的，而且遍历时，保持子串长度相同，先递增母串长度，母串最长时再增加一点子串长度重头开始计算母串。
这个问题实际上是问一个长字符串中有几个给定的子串，因此从开始比较，以最后一个字符为例，如果T的最后一个字符和S的最后一个字符不相同，那么问题就成为求字符串S[:-2]中字符T的个数；如果相同，问题就变为求字符串S[:-2]中字符T的个数和S[:-2]中子串T[:-2]的个数之和。从后向前递推，我们可以得到下面的矩阵
0 r a b b b i t
0 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
首先我们先要初始化矩阵，当子串长度为0时，所有次数都是1，当母串长度为0时，所有次数都是0.当母串子串都是0长度时，次数是1（因为都是空，相等）。接着，如果子串的最后一个字母和母串的最后一个字母不同，说明新加的母串字母没有产生新的可能性，可以沿用该子串在较短母串的出现次数，所以dp(i)(j) = dp(i)(j-1)。如果子串的最后一个字母和母串的最后一个字母相同，说明新加的母串字母带来了新的可能性，我们不仅算上dp(i)(j-1)，也要算上新的可能性。那么如何计算新的可能性呢，其实就是在既没有最后这个母串字母也没有最后这个子串字母时，子串出现的次数，我们相当于为所有这些可能性都添加一个新的可能。所以，这时dp(i)(j) = dp(i)(j-1) + dp(i-1)(j-1)。
public int numDistinct(String s, String t) {
int n = s.length(), m = t.length();
int[][] dp = new int[m+1][n+1];
for(int j = 0; j < n; j++){
dp[0][j] = 1;
}
for(int i = 1; i < m+1; i++){
for(int j = 1; j < n+1; j++){
if(s.charAt(j-1)==t.charAt(i-1)){
dp[i][j] = dp[i-1][j-1]+dp[i][j-1];
} else {
dp[i][j] = dp[i][j-1];
}
}
}
return dp[m][n];
}