Description

Submission

class Solution {
    int dp[100005][3][2];
public:
    int checkRecord(int n) {
        // number of total A's and consecutive L's
        vector<vector<long>> dp(2, vector<long>(3, 0));
        dp[0][0] = 1;
        auto dp2 = dp;

        const long M = 1e9 + 7;

        for(int i = 1; i <= n; ++i) {
            dp[0][0] = (dp2[0][0] + dp2[0][1] + dp2[0][2]) % M;
            dp[0][1] = dp2[0][0];
            dp[0][2] = dp2[0][1];
            dp[1][0] = (dp2[0][0]+ dp2[0][1] + dp2[0][2] + dp2[1][0] + dp2[1][1] + dp2[1][2]) % M;
            dp[1][1] = dp2[1][0];
            dp[1][2] = dp2[1][1];
            
            dp2 = dp;
        }

        return (dp[0][0] + dp[0][1] + dp[0][2] + dp[1][0] + dp[1][1] + dp[1][2]) % M;
    }
};


// n = 3

// AA X
// AL
// AP
// LA