给出字符串S和字符串T，计算S的不同的子序列中T出现的个数。
子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串，并且对剩下的字符的相对位置没有影响。(比如，“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)。
样例
给出S = "rabbbit", T = "rabbit"
返回 3
分析：
首先想到的是深度优先搜索，递归找出所有可能的情况，结果超时
然后从动态规划方面考虑
如果只匹配最后一位字符T[n]，则在S中T[n]出现了几次就有几种方式
若匹配后两位则是T[n-1]在S中出现且后面有T[n]所有的情况
依次类推，可以得到答案
class Solution { public: /** * @param S, T: Two string. * @return: Count the number of distinct subsequences */ /* int numDistinct(string &S, string &T) { // write your code here int num = 0; sub(S, T, 0, 0, num); return num; } void sub(string &S, string &T, int p1, int p2, int &num) { if(p2 >= T.size()) { num += 1; return; } char t = T[p2]; for(int i = p1; i < S.size(); ++i) { if(S[i] == t) { sub(S, T, i + 1, p2 + 1, num); } } } */ int numDistinct(string &S, string &T) { // write your code here if(T.size() == 0) return 1; vector<int> buf(S.size(), 0); int pos = T.size() - 1; int num = 1; while(pos >= 0) { char t = T[pos]; for(int i = buf.size() - 1; i >= 0; --i) { if(S[i] == t) { int tmp = buf[i]; buf[i] = num; num += tmp; }else { num += buf[i]; buf[i] = 0; } } --pos; num = 0; } num = 0; for(int i = 0; i < buf.size(); ++i) { num += buf[i]; } return num; } };
