EEPW论坛

Given a string S and a string T, count the number of distinct subsequences ofT 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"

Return3.

思路：动态规划思想

dp[i][j]表示S中前i个字符构成的字符串包含T中前j个字符构成的字符串的长度，

当s[i-1]==T[j-1]时，则新的dp值可以说不使用第i个字符，却能构成T中j子串

1. class Solution {  

2. public:  

3.     int numDistinct(string S, string T)  

4.     {  

5.         int slen = S. length();  

6.         int tlen = T.length();  

7.   

8.         vector<vector<int>> dp;  

9.         vector<int> tmp(tlen+1, 0);  

10.         tmp[0] = 1;  

11.   

12.         for (int i=0; i<=slen; i++)  

13.         {  

14.             dp.push_back(tmp);  

15.         }  

16.   

17.         for (int i=1; i<=slen; i++)  

18.         {  

19.             for(int j=1; i<=tlen; j++)  

20.             {  

21.                 if (S[i-1]==T[j-1])  

22.                 {  

23.                     dp[i][j] = dp[i-1][j] + dp[i-1][j-1];  

24.                 }  

25.                 else  

26.                 {  

27.                     dp[i][j] = dp[i-1][j];  

28.                 }  

29.             }  

30.         }  

31.   

32.         return dp[slen][tlen];  

33.     }  

34.       

35. };