C++ DP short solution


  • 0
    W

    Inspired by @zym_ustc to finish my algorithm.

    Step 1. calculate the number of valid sequences without A, which will end with P, with L and with LL. The result is the sum of these three states.

    Step 2. insert A into the sequence, there are n positions to put A. Suppose we put A at location i, on the left side of A, there are i-1 positions to fill without A; on the right side of A, there are n-i positions to fill without A. Here we reuse the results from step 1.

    class Solution {
    public:
        int checkRecord(int n) {
            if (n==1) return 3;
            vector<int> endP(n+1,0), end1L(n+1,0), end2L(n+1,0), noA(n+1,1);
            endP[1] = 1; end1L[1] = 1; end2L[1] = 0; noA[1] = 2;
            for (int i=2; i<=n; i++){
                endP[i] = add( add(endP[i-1],end1L[i-1]), end2L[i-1]);
                end1L[i] = endP[i-1];
                end2L[i] = end1L[i-1];
                noA[i] = add( add(endP[i],end1L[i]), end2L[i]);
            }
            int withA = 0;
            for (int i=1; i<=n; i++){
                withA = add(withA, ((long long)noA[i-1]*noA[n-i])%1000000007);
            }
            return add(withA, noA[n]);
        }
        
        int add(int a, int b){
            return (a%1000000007 + b%1000000007)%1000000007;
        }
    };
    

Log in to reply
 

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