> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/duo-zhuang-tai-dp/552.-student-attendance-record-ii.md).

# 552. Student Attendance Record II

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

由L、A、P组成的长度为n的字符串，不能出现连续3个或以上的L，最多出现一个A，有多少个这样的字符串。这里直接引用[冒泡](https://www.zhihu.com/question/39948290/answer/83942329)的解法:

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

```cpp
/*
 * @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;
    }
};


```