Untitled

class Solution {
public:
    vector<vector<long long>> dp;
    int numDistinct(string s, string t) {

        long long m = s.size();
        long long n = t.size();

        dp.assign(m+1, vector<long long>(n+1,-1)); // doing +1 as working with 0 index is hard
        // same logic as when doing for LCS

        // base case
        for(long long j=0; j<=n; j++){
            dp[m][j] = 0;
            // i == m, so return 0
        }
        for(long long i=0; i<=m; i++){
            dp[i][n] = 1;
            // j == n, so return 1
        }
        for(long long i=m-1; i>=0; i--){
            for(long long j=n-1; j>=0; j--){
                dp[i][j] = dp[i+1][j];

                if(s[i] == t[j]){
                    dp[i][j] += dp[i+1][j+1];
                } 
            }
        }

        return dp[0][0];
    }
};