/*****

下标从1开始

dp[i][j]:= numbers of subseq of S[1:j] equals T[1:i]

if(s[j]==t[i]):(那么之后的子串可以是是dp[i-1][j-1](match) 或dp[i][j-1] (not match))

    dp[i][j]=dp[i-1][j-1]+

                dp[i][j-1];

if(t[i]!=s[j]):

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

初始化：

dp[0][*]=0

时间：O(n2) 空间O(n2)

使用滚动数组：

O(n)空间：

*****/

class Solution {

public:

    int numDistinct(string s, string t) {

        int ls=s.length(),lt=t.length();

        vector<long> dp(ls+,);

        for(int i=;i<=lt;i++){

            int pre=dp[],cur;

            dp[]=;

            for(int j=;j<=ls;j++){

                cur=dp[j];

                if(s[j-]==t[i-])

                    dp[j]=pre+dp[j-];

                else

                    dp[j]=dp[j-];

                pre=cur;

                //cout<<dp[j]<<" ";

            }

            //cout<<endl;

        }

        return dp[ls];

    }

};

/*****

下标从1开始

dp[i][j]:= numbers of subseq of S[1:j] equals T[1:i]

if(s[j]==t[i]):(那么之后的子串可以是是dp[i-1][j-1](match) 或dp[i][j-1] (not match))

    dp[i][j]=dp[i-1][j-1]+

                dp[i][j-1];

if(t[i]!=s[j]):

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

初始化：

dp[0][*]=0

时间：O(n2) 空间O(n2)

使用滚动数组：

O(n)空间：

*****/

class Solution {

public:

    int numDistinct(string s, string t) {

        int ls=s.length(),lt=t.length();

        vector<vector<long>> dp(lt+,vector<long>(ls+));

        fill(begin(dp[]),end(dp[]),);

        for(int i=;i<=lt;i++){

            for(int j=;j<=ls;j++){

                if(s[j-]==t[i-])

                    dp[i][j]=dp[i-][j-]+dp[i][j-];

                else

                    dp[i][j]=dp[i][j-];

                //cout<<dp[i][j]<<" ";

            }

            //cout<<endl;

        }

        return dp[lt][ls];

    }

};