https://leetcode.com/problems/distinct-subsequences/

 

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.

 

定义f[i][j]表示在S[0,i]中，T[0,j]出现了几次。无论s[i]和t[j]是否相等，如果不匹配s[i]，则f[i][j]=f[i-1][j];若s[i]==s[j]，

f[i][j]=f[i-1][j]+[i-1][j-1]。

另外，当t=""时，只有一种匹配方式，f[i][0]=1；当s="",t!=""时，无论如何无法匹配，此时f[0][j]=0。

 参考：http://www.cnblogs.com/yuzhangcmu/p/4196373.html

int numDistinct(string s, string t) {        int m=s.size();        int n=t.size();                vector
     
      
       > f(m+1,vector
       
        (n+1,0));                for(int i=0;i<=m;i++)        {            for(int j=0;j<=n;j++)            {                if(i==0 && j==0)                  f[i][j]=1;                else if(i==0)                  f[i][j]=0;                else if(j==0)                  f[i][j]=1;                else                f[i][j]=f[i-1][j]+(s[i-1]==t[j-1]?f[i-1][j-1]:0);            }        }        return f[m][n];    }