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"
Return 3.
1 class Solution { 2 public: 3 int numDistinct(string s, string t) { 4 int lenS=s.size(); 5 int lenT=t.size(); 6 7 vector<vector<int> >f(lenS+1,vector<int>(lenT+1,0)); 8 9 for(int i=0;i<=lenS;i++) f[i][0]=1; 10 11 for(int i=1;i<=lenS;i++) 12 { 13 for(int j=1;j<=lenT;j++) 14 { 15 if(s[i-1]==t[j-1]) 16 f[i][j]=f[i-1][j-1]+f[i-1][j]; 17 else 18 f[i][j]=f[i-1][j]; 19 } 20 } 21 22 return f[lenS][lenT]; 23 24 25 } 26 };
【leetcode】Distinct Subsequences
原文：http://www.cnblogs.com/jawiezhu/p/4558128.html