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)…

Distinct Subsequences.cpp

class Solution {
public:
    int dp[100][10000];
    string S;
    string T;

    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        memset(dp, -1, sizeof(dp));
        this->S = S;
        this->T = T;
        int res = search(0, 0);
        return res;
    }
    
    int search(int index, int sss) {
        if(index == T.length()) {
            return 1;
        }
        
        if(dp[index][sss] == -1) {
            int res = 0;
            char cur = T[index];
            for(int j = sss; j < S.length(); ++j) {
                if(cur == S[j]) {
                    res += search(index + 1, j + 1);
                }
            }
            dp[index][sss] = res;
        }
        return dp[index][sss];
    }
};