552. Student Attendance Record II

https://leetcode.com/problems/redundant-connection-ii/description/

由L、A、P组成的长度为n的字符串，不能出现连续3个或以上的L，最多出现一个A，有多少个这样的字符串。这里直接引用冒泡的解法:

很明显需要n步决策，每次决策时候要从3个字母里面选合法的，P任何情况都合法，A在没出现过的情况下合法，L则在现有串最后不是AA时候合法，因此状态就是是否出现过A和最后两个字母中L的分布情况的一个组合，A是否出现有两个值，L的分布有**，*L，LL三种（*代表A或P，不用展开了），所以就是2*3=6种状态啦

/*
 * @lc app=leetcode id=552 lang=cpp
 *
 * [552] Student Attendance Record II
 */
class Solution {
public:
    int checkRecord(int n) {
        const int M = 1000000007;
        // 截止到i，分别以A, L, P结尾的状态。
        vector<long> A0L0(n + 1), A0L1(n + 1), A0L2(n + 1), A1L0(n + 1), A1L1(n + 1), A1L2(n + 1);
        A0L0[0] = 1;
        for (int i = 1; i <= n; ++i) {
            // 放P
            A0L0[i] =  (A0L0[i - 1] + A0L1[i - 1] + A0L2[i - 1]) % M;
            // 放L
            A0L1[i] = A0L0[i - 1];
            // 放L
            A0L2[i] = A0L1[i - 1];
            // 放A或P
            A1L0[i] = (A0L0[i - 1] + A0L1[i - 1] + A0L2[i - 1] + A1L0[i - 1] + A1L1[i - 1] + A1L2[i - 1]) % M; 
            // 放L
            A1L1[i] = A1L0[i - 1];
            // 放L
            A1L2[i] = A1L1[i - 1];
        }
        return (A0L0[n] + A0L1[n] + A0L2[n] + A1L0[n] + A1L1[n] + A1L2[n]) % M;
    }
};