Distinct Subsequences

 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.

解析：

开始用递归，超时，动态规划

dp[i][j]表示从t的第i元素之后的串与s的j之后的串的满足条件的个数，那么此题求dp[0][0]

如果t[i]==s[j]，则dp[i][j]=dp[i+1][j+1]+dp[i][j+1]，否则的话dp[i][j]=dp[i][j+1]，注意初始边界条件

代码：

class Solution {
public:
    
    int cntNum(string& s,string& t,int sbegin,int tbegin,vector<vector<int>>&vis)
    {
        if (vis[sbegin][tbegin]) return vis[sbegin][tbegin];
        int slen=s.size();
        int tlen=t.size();
        
        if ((slen-sbegin)<(tlen-tbegin)) return 0;
        if (tbegin==tlen)
        {
           // vis[sbegin]
            return 1;
        }
        
        if (s[sbegin]==t[tbegin])
        {
            if (sbegin==(slen-1)&&tbegin==(tlen-1))
            {
                vis[sbegin][tbegin]=1;
                return 1;
            }
            int sum=0;
            if (vis[sbegin+1][tbegin+1])
            sum+=vis[sbegin+1][tbegin+1];
            else
            {
                vis[sbegin+1][tbegin+1]=cntNum(s,t,sbegin+1,tbegin+1,vis);
                sum+=vis[sbegin+1][tbegin+1];
            }
           
            if (vis[sbegin+1][tbegin])
            {
                sum+=vis[sbegin+1][tbegin];
            }
            else
            {
                vis[sbegin+1][tbegin]=cntNum(s,t,sbegin+1,tbegin,vis);
                sum+=vis[sbegin+1][tbegin];
            }
            vis[sbegin][tbegin]=sum;
            return vis[sbegin][tbegin];
        }
        vis[sbegin][tbegin]=cntNum(s,t,sbegin+1,tbegin,vis);
        return  vis[sbegin][tbegin];
        
    }
    int numDistinct(string s, string t) {
        
        if (s.empty()||t.empty()) return 0;
        int slen=s.size();
        int tlen=t.size();
        vector<vector<int>>dp(tlen+1,vector<int>(slen+1,0));
        dp[tlen][slen]=1;
        if (slen<tlen) return 0;
        if (slen==tlen&&s==t) return 1;
        
       // if (s[slen-1]==t[tlen-1]) dp[tlen-1][tlen-1]=1;
        int cnt=1;
        for (int i=slen; i>=tlen; i--)
        {
            dp[tlen][i]=1;
        }
        
        for (int i=tlen-1; i>=0; i--)
        {
            for (int j=slen-1; j>=i; j--)
            {
                if (t[i]==s[j])
                {
                    dp[i][j]=dp[i+1][j+1]+dp[i][j+1];
                }
                else
                {
                    dp[i][j]=dp[i][j+1];
                }
            }
        }
        
        
        return dp[0][0];
        
        
     //   vector<vector<int>>vis(slen+1,vector<int>(tlen+1,0));
     //   return  cntNum(s,t,0,0,vis);
    }
};