115. Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/

Solution:

Need dynamic programming (dp). The key is to find the transition equation. Let suppose dp[i][j] represents the number of distinct subsquences in the first i elements of s for the first j elements of t. When t[j] != s[i], then s[i] cannot be used, and dp[i+1][j+1] = dp[i][j+1]; if t[j] == s[i], then s[i] can be either used nor not used, and dp[i+1][j+1] = dp[i][j] + dp[i][j+1]; so,

                          

         dp[i+1][j+1] = dp[i][j+1];                 if(s[i] ! = t[j])
                      = dp[i][j] + dp[i][j+1];      else

And the space can be further optimized to O(n).

Code:

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(),  n = t.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=0; i<=m; ++i) dp[i][0] = 1;  //empty string is always a valid sub-sequence.
        for(int i=1; i<=n; ++i) dp[0][i] = 0;   //Non-empty string is always non-valid .. for an empty str.
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(s[i] == t[j]) dp[i+1][j+1] = dp[i][j] + dp[i][j+1];
                else dp[i+1][j+1] = dp[i][j+1];
            }
        }
        return dp[m][n];
    }
};