[552. Student Attendance Record II] C++_with explanation_from DFS to DP


  • 4

    This problem is not so hard... but you have to be aware of lots of details, like memory limit, number's out of range and etc.

    First, I tried the DFS method. Of course, it is TLE.

    class Solution {
    public:
    int checkRecord(int n) {
        long long res = 0;
        dfs(n, 0, 0, 0, res);
        return res % (int(pow(10,9))+7);
    }
    void dfs(int n, int s, int A, int L, long long& res){
        if(s == n){
            res++;
            return;
        }
        dfs(n, s+1, A, 0, res);//add "P"
        if(A < 1){
            dfs(n, s+1, A + 1, 0, res);
        }
        if(L <= 1){
            dfs(n, s+1,A, L + 1, res);
        }
    }
    };
    

    So I switched to Dynamic Programming, the status functions are:
    dp[n][j][k] : The current total length of our string is n, in current string s, the number of 'A' is j, of course j = 0 or 1, and the number of continuous L at the end of our string is k, k = 0, 1, 2.
    Each time we will add one char at the end of our current string.

     (1) dp[n][0][0] = dp[n-1][0][0] + dp[n-1][0][1] + dp[n-1][0][2] 
     3 ways we can get length n string with 0 'A' and 0 continuous L at the end of string s: add 1 "P" at the end of  dp[n-1][0][0], dp[n-1][0][1], dp[n-1][0][2]
    
     (2) dp[n][0][1] = dp[n-1][0][0]
     We could only reach this status from dp[n-1][0][0] by add one 'L'
    
     (3) dp[n][0][2] = dp[n-1][0][1] 
     We could only reach this status from dp[n-1][0][1] by add one 'L'
      
     (4) dp[n][1][0] = dp[n-1][0][0] (add one 'A' after the 'P') + 
                         dp[n-1][0][1](add one 'A' after the 'L') + 
                         dp[n-1][0][2](add one 'A' after the 'LL')
                         dp[n-1][1][0](add one 'P' after 'P') + 
                         dp[n-1][1][1](add one 'P' after 'L') + 
                         dp[n-1][1][2](add one 'P' after 'LL')
    
    
     (5) dp[n][1][0] = dp[n-1][0][0] (add one 'A' after 'P') + 
                          dp[n-1][0][1](add one 'A' after 'L') + 
                          dp[n-1][0][2](add one 'A' after 'LL')
                          dp[n-1][1][0](add one 'P' after 'P') + 
                          dp[n-1][1][1](add one 'P' after 'L') + 
                          dp[n-1][1][2](add one 'P' after 'LL')
                  
     (6) dp[n][1][1] = dp[n-1][1][0]
      (add one 'L' after 'P' or 'A', and at n-1, we've already have one 'A' in our string)
    
     (7) dp[n][1][2] = dp[n-1][1][1]
       (add one 'L' after 'L', and at n-1, we've already have one 'A' in our string)
    
     (initial) dp[1] = [
                 [1,1,0], 
    

    //no 'A' in our string: The ending have 0 continuous 'L', which is 'P';
    The ending have 1 continuous 'L', which is 'L';
    The ending have 2 continuous 'L', which is impossible.

                 [1,0,0]
    

    //one 'A' in our string: The ending have 0 continuous 'L', which is 'A';
    The ending have 1 continuous 'L', which is impossible;
    The ending have 2 continuous 'L', which is impossible.
    ]

    What's more, we notice that dp is only dependent on n-1, so we can use 2-dimensional vector to conduct our dynamic programming.

    One thing we mush be aware is that number in our vector will be pretty large!!! So just try to mod M at each summation step.

    The C++ code:

     class Solution {
     public:
    int checkRecord(int n) {
        const int M = 1000000007;
        vector< vector<long> > dp(2, vector<long>(3, 0));
        dp = {{1,1,0},{1,0,0}};
        for(int i = 1; i < n; ++i){
            vector< vector<long> > tmp(2, vector<long>(3, 0));
            tmp[0][0] = ((dp[0][0] + dp[0][1] + dp[0][2])%M);
            tmp[0][1] = dp[0][0]%M;
            tmp[0][2] = dp[0][1];
            tmp[1][0] = (((dp[0][0] + dp[0][1] + dp[0][2])%M + (dp[1][0] + dp[1][1] + dp[1][2])%M))%M;
            tmp[1][1] = dp[1][0]%M;
            tmp[1][2] = dp[1][1]%M;
            dp = tmp;
        }
        long res = 0;
        for(int A = 0; A < 2; ++A){
            for(int L = 0; L < 3; ++L){
                res += dp[A][L]%M;
            }
        }
        return res%M;
    }
    };

  • 0
    L

    Could you explain the [1,1,0 ] and [1,0,0]. I followed your logic up till that point


  • 1

    @livelearn

    Hi, dp[1] is the initial status, which is the current string length is 1. So we can analyze all of possibilities for this length.
    Recall: dp[n][j][k] : The current total length of our string is n, in current string s, the number of 'A' is j, of course j = 0 or 1, and the number of continuous L at the end of our string is k, k = 0, 1, 2.

    dp[1][0][0] = 1; no 'A', and at the end of this string, there is 0 continuous 'L', so the string can only be 'P', so dp[1][0][0] is 1.

    dp[1][0][1] = 1; no 'A', and at the end of this string, there is 1 continuous 'L', so the string can only be 'L', so dp[1][0][1] is 1.

    dp[1][0][2] = 0; because we only have length 1 string, the case that 2 continuous 'L' at the end of the string is impossible.

    dp[1][1][0] = 1; only 1 unit of 'A' in our string, and there is 0 continuous 'L' at the end, so current string can only be 'A'.

    dp[1][1][1] = 0; 1 unit of 'A' and 1 continuous 'L' at the end of string, totally length is 2, so it is impossible.

    dp[1][1][2] = 0; similar as above.

    Is it clear for you? If you still have any question, please feel free to contact me.


  • 0
    B

    @jasonshieh Nice explanation, step 5 is duplicate of step 4. This DP problem became much more intuitive after writing/visualizing DFS call tree.


Log in to reply
 

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