DP solution, simple C++ code, and the scroll array optimization with clear explaination


  • 0
    P

    We define dp[i, j] as the number of subsequence with the first i elements in S, and the jth element as tail in T.
    dp[i, j] = dp[i - 1, j] if(S[i] != T[j])
    dp[i, j] = dp[i - 1, j] + dp[i - 1, j - 1] if(S[i] == T[j])

    So we can get the code

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

    However, we can find dp[i, j] depends on dp[i - 1, j] and dp[i - 1, j - 1], if we can compute the dp[i - 1, j] and dp[i - 1, j - 1] before dp[i, j], we only need one dimension array. If we draw 2D array, the ascending order i and descending order j are the one of the correct choices. We call this method as the scroll array.

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.