lintcode

给出字符串S和字符串T，计算S的不同的子序列中T出现的个数。

子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串，并且对剩下的字符的相对位置没有影响。(比如，“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)。

样例

给出S = "rabbbit", T = "rabbit"

返回 3

 1 class Solution {
 2 public:
 3     /*
 4      * @param : A string
 5      * @param : A string
 6      * @return: Count the number of distinct subsequences
 7      */
 8      int dp[220][220];
 9     int numDistinct(string S, string T) {
10         // write your code here
11         if(T.size() == 0) return 1;
12         else if(S.size() == 0) return 0;
13 
14         memset(dp,0,sizeof(dp));
15 
16         for(int i = 0; i < S.size(); ++i){
17                 if(S[i] == T[0]) dp[i][1] += 1;
18         }
19         int len = T.length();
20         for(int i = 1; i < S.length(); ++i){
21                 for(int j = 1; j <= len && j <= i + 1; ++j){
22                                 if(S[i] == T[j-1]){
23                                         dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
24                                         //printf("%d %d %d
",dp[i][j],i,j);
25 
26                                 }
27 
28                         dp[i][j] += dp[i-1][j];
29                 }
30         }
31         return dp[S.length() - 1][len];
32     }
33 };

dp[i][j] 表示，在S串中以 i 结尾时，长度为j的T的子串在S中的个数。

比如 S = “abcd” T = “” S长度为6，T长度为2

dp[5][2]，代表S串以5结尾，S[5] 是 "，长度为2的T是 "" ，在S中的个数为 1。也就是整个S串里，有1个T串。

dp[i][j]由什么计算出来呢？两部分，第一部分是当 S[i] == T[j-1](j是长度) dp[i-1][j-1] 也就是以 i-1结尾的长度为j-1的T的子串的个数第二部分是 dp[i-1][j] 也就是前i-1里长度为J的个数