C++ less than 10 lines dp solution with explanation


  • 4

    This is similar to Edit Distance problem we solved before, which also needs to build dp array, however, here, from s to t, we can only perform delete operation.

    dp array: dp[i][j] means the number of distinct subsequences of t.substr(0, i) in s.substr(0,j). if i = 0, t.substr(0,0) = "", we can say there are 1 instance of that for "". So, initialize dp[0][j] = 1, and other dp[i][j] = 0.

    dp[1][1]: how many A in "A"? It's obvious, dp[1][1] = 1;

    dp[1][2]: how many A in "AE"? It's obvious, dp[1][2] = dp[1][1] = 1;

    dp[1][3]: how many A in "AECD"? similarly, dp[1][3] = dp[1][2];

    ... ...

    dp[2][6]: how many "AE" in "AECDEE"? Since the end of "AECDEE" matches end of "AE", consider the purpose we build dp, we want to use the result we already calculated, so we can split this into two subproblems:

    1. if 'E' in "AE" comes from last 'E' in "AECDEE"

    here, we can then disregard the last 'E' in both sub-string, the answer for this subproblem should be equivalent to calc dp[i - 1][j - 1]: how many "A" in "AECDE"?

    1. if 'E' in "AE" comes from "AECDE"

    here, the answer for this subproblem should be equivalent to calc dp[i][j - 1]: how many "AE" in "AECDE"?

    dp[2][6] = dp[1][5] + dp[2][5] = 1 + 2 = 3
    

    Based on above scenarios, we get the following generalized rules

    if t[i - 1] == s[j - 1] dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]
    else dp[i][j] = dp[i][j - 1]
    

    Build dp array

             A E C D E E C E
           0 1 2 3 4 5 6 7 8
    
       0   1 1 1 1 1 1 1 1 1
    
     A 1   0 1 1 1 1 1 1 1 1
     E 2   0 0 1 1 1 2 
     C 3   
    

    Final table

             A E C D E E C E
           0 1 2 3 4 5 6 7 8
    
       0   1 1 1 1 1 1 1 1 1
    
     A 1   0 1 1 1 1 1 1 1 1
     E 2   0 0 1 1 1 2 3 3 4
     C 3   0 0 0 1 1 1 1 4 4
    

    Code

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

  • 0
    V

    Nice explanation. Still one problem : your code can be ACed in OJ, but running in IDE I got exception thrown because s[j-1] would be s[-1] when j==0 within the loop. Strange it didn't cause any error in OJ.


Log in to reply
 

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