LeetCode 115. Distinct Subsequences [Analysis]

Here is the problem.

Note that simply generating all the subsequences of S is not going to work because there are a total of 2^|S| number of subsequences. We break this problem down into a dynamic programming problem as follows:

dp[i][j] = number of subsequences of s[0…i] that matches the string t[0…j].

Then we can form the following recursive relationships:

If s[i] == t[j]:  

dp[i][j] = dp[i][j] + dp[i-1][j-1] + dp[i-1][j], 
because the ith character of s can be used to match the jth character of t or not match 
the jth character of t (in which case we move over to the i-1th character of s).  

Else: 

dp[i][j] = dp[i][j] + dp[i-1][j], because we have no choice but to not use the ith character of s.  

Note that I have used the long long data type in C++ as the answer may get really big.

Time Complexity: O(nm), where n = |S|, m = |T|.

C++ Code:

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size(); 
        long long dp[n+1][m+1]; 
        memset(dp,0,sizeof(dp));  
        for (int i = 0; i <= n; i++){
            dp[i][0] = 1LL;  
        }
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (s[i-1] == t[j-1]){
                    dp[i][j] += dp[i-1][j-1]+dp[i-1][j];  
                }else{
                    dp[i][j] += dp[i-1][j];  
                }
            }   
        }
        return dp[n][m]; 
    }
};