Given two strings s and t, return the number of distinct subsequences of s which equals t.

A string's subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters' relative positions. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).

The test cases are generated so that the answer fits on a 32-bit signed integer.

&nbsp;
Example 1:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
rabbbit
rabbbit
rabbbit


Example 2:

Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
babgbag
babgbag
babgbag
babgbag
babgbag

&nbsp;
Constraints:


	1 &lt;= s.length, t.length &lt;= 1000
	s and t consist of English letters.


class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(t) > len(s):
            return 0
        ls, lt = len(s), len(t)
        res = 0
        dp = [[0] * (ls + 1) for _ in range(lt + 1)]
        for j in range(ls + 1):
            dp[-1][j] = 1
        for i in range(lt - 1, -1, -1):
            for j in range(ls -1 , -1, -1):
                dp[i][j] = dp[i][j + 1]
                if s[j] == t[i]:

                    dp[i][j] += dp[i + 1][j + 1]
        return dp[0][0]
class Solution {
    // We assume that dp[i][j] gives us the total number of distinct subsequences for the string s[0 to i] which equals string t[0 to j]
    int f(int i,int j,String s,String t,int dp[][]){
        //If t gets exhausted then all the characters in t have been matched with s so we can return 1 (we found a subsequence)
        if(j<0)
            return 1;
        // if s gets exhausted then there are characters remaining in t which are yet to be matched as s got exhausted they could not be matched so there is no distinct subsequence
        if(i<0){
            return 0;
        }
        if(dp[i][j]!=-1)
            return dp[i][j];
        //If both the characters in s[i] and t[j] match then we have two case
            //1) Either consider the i'th character of s and find the remaining distinct subsequences of s[0 to i-1] which equals t[0 to j-1] set i.e. f(i-1,j-1)
            //2) Do not consider s[i] so we are still at the same j'th character of t as we had not been considering s[i] matched with t[j] we check distinct subsequences of t[0 to j] in s[0 to i-1] i.e. f(i-1,j)
        if(s.charAt(i)==t.charAt(j)){
            dp[i][j]= f(i-1,j-1,s,t,dp)+f(i-1,j,s,t,dp);
        }
        // If both of them do not match then we consider the 2nd case of matching characters
        else{
            dp[i][j]=f(i-1,j,s,t,dp);
        } 
        return dp[i][j];
    }
    public int numDistinct(String s, String t) {
        int n=s.length();
        int m=t.length();
        int dp[][]=new int[n][m];
        for(int i=0;i<n;i++){
            Arrays.fill(dp[i],-1);
        }
        return f(n-1,m-1,s,t,dp);
    }
}
class Solution {
public:
    int solve(string &s, string &t, int i, int j, vector<vector<int>> &dp){
        if(j >= t.size()) return 1;
        if(i >= s.size() || t.size() - j > s.size() - i) return 0;
        if(dp[i][j] != -1) return dp[i][j];
        int res = 0;
        for(int k = i; k < s.size(); k++){
            if(s[k] == t[j]) res += solve(s, t, k+1, j+1, dp); 
        }
        return dp[i][j] = res;
    }
    
    int numDistinct(string s, string t) {
        if(s.size() == t.size()) return s == t;
        vector<vector<int>> dp(s.size(), vector<int> (t.size(), -1));
        return solve(s, t, 0 , 0, dp);
    }
};
var numDistinct = function(s, t) {
    const n = s.length;

    const memo = {};
    const dfs = (index = 0, subsequence = '') => {
        if(subsequence === t) return 1;
        if(n - index + 1 < t.length - subsequence.length) return 0;
        if(index === n) return 0;

        const key = `${index}-${subsequence}`;
        if(key in memo) return memo[key];

        memo[key] = t[subsequence.length] !== s[index] ? 0 : dfs(index + 1, subsequence + s[index]);
        memo[key] += dfs(index + 1, subsequence);
        return memo[key];
    }

    return dfs();
};
Distinct Subsequences