C++ 10 lines, O(n) DP, 29ms, comments inline


  • 0
    S
    class Solution {
    public:
        int checkRecord(int n) {
            //a0[0]=1, a1[0]=0;
            //a0[1]=2, a1[1]=1;
            //a0[2]=4, a1[2]=4;
            //a0[i]= a0[i-1] // +p
            //       + a0[i-2] //+PL
            //       + a0[i-3] //+PLL,
            //a1[i]= a0[i-1]  -- +A
            //       + a1[i-1] -- +P
            //       + a1[i-2] -- +PL
            //       + a1[i-3] -- +PLL
            //       + a0[i-2] -- +AL
            //       + a0[i-3] -- +ALL
            vector<long> A0(n+1, 1), A1(n+1,0);
            A0[1]=2; A1[1]=1;
            A0[2]=4; A1[2]=4;
            for (int i=3; i<=n; i++) {
                A0[i]=(A0[i-1] + A0[i-2] + A0[i-3]) % (long)1000000007;
                A1[i]= (A0[i-1] + A1[i-1] + A1[i-2] + A1[i-3] + A0[i-2] + A0[i-3]) % (long)1000000007;
            }
            return (A0.back() + A1.back())% (long)1000000007;
        }
    };
    

  • 0
    S

    A0[i] is the number of sequences with length i that does not have 'A'.
    A1[i] is the number of sequences with length i that has only one 'A'.


  • 0
    A

    @sgsg You should point out that you are using undocumented behavior of the C++ vectors for the base cases. That's why you are able to use vector::back() even for the base cases.


Log in to reply
 

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