30.Distinct Subsequences

 class Solution {

public:

int func(int n,int m,string &s,string &t,vector<vector<int>>&dp)

{

     if(m<0)return 1;

    if(n<0)return 0;

    

    if(dp[n][m]!=-1)return dp[n][m];

    if(s[n]==t[m])

    {

          return dp[n][m]=func(n-1,m-1,s,t,dp)+func(n-1,m,s,t,dp);

    }

    return dp[n][m]=func(n-1,m,s,t,dp);

}

    int numDistinct(string s, string t) 

    {

       

        vector<vector<int>>dp(s.size(),vector<int>(t.size(),-1));

         return func(s.size()-1,t.size()-1,s,t,dp);

    }

};