# 552.学生出勤记录 II (Hard)

## 问题描述
[552. 学生出勤记录 II (Hard)](https://leetcode.cn/problems/student-attendance-record-ii/)

可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

- `'A'`：Absent，缺勤
- `'L'`：Late，迟到
- `'P'`：Present，到场

如果学生能够 **同时** 满足下面两个条件，则可以获得出勤奖励：

- 按 **总出勤** 计，学生缺勤（ `'A'`） **严格** 少于两天。
- 学生 **不会** 存在 **连续** 3 天或 **连续** 3 天以上的迟到（ `'L'`）记录。

给你一个整数 `n` ，表示出勤记录的长度（次数）。请你返回记录长度为 `n` 时，可能获得出勤奖励的记录情况
**数量** 。答案可能很大，所以返回对 `10⁹ + 7` **取余** 的结果。

**示例 1：**

```
输入：n = 2
输出：8
解释：
有 8 种长度为 2 的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。

```

**示例 2：**

```
输入：n = 1
输出：3

```

**示例 3：**

```
输入：n = 10101
输出：183236316

```

**提示：**

- `1 <= n <= 10⁵`

## 解题思路
### dp思路1
考虑`dp2[i][0]`为只有迟到和到场两种情况下，第`i + 1`天迟到的情况数，`dp2[i][1]`为第`i + 1`天到场的情况数，则递推关系为:
- `dp2[i][1] = dp2[i - 1][0] + dp2[i - 1][1];`
- `dp2[i][0] = dp2[i - 1][1] + dp2[i - 1][0] - dp2[n - 3][1];`

考虑`dp[i][0]`为第`i + 1`天迟到的情况数，`dp[i][1]`为第`i + 1`天到场的情况数，`dp[i][2]`为第`i + 1`天缺席的情况数，则递推关系有：
- `dp[i][1] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];`
- `dp[i][2] = dp2[i - 1][0] + dp2[i - 1][1];`
- `dp[i][0] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][0] - (dp[i - 3][1] + dp[i - 3][2]);`

注意取模

### dp思路2

## 代码
```cpp
class Solution {
  public:
    int checkRecord(int n) {
        if (n == 1)
            return 3;
        if (n == 2)
            return 8;
        if (n == 3)
            return 19;
        vector<vector<long long>> dp3(n + 1, vector<long long>(3, 0));
        vector<vector<long long>> dp2(n, vector<long long>(2, 0));
        int mod = 1000000007;
        // 0表示迟到，1表示到场，2表示缺勤
        dp2[0][0] = dp2[0][1] = 1;
        dp2[1][0] = dp2[1][1] = 2;
        dp2[2][0] = 3;
        dp2[2][1] = 4;
        for (int i = 3; i < n; i++) {
            dp2[i][1] = (dp2[i - 1][0] % mod + dp2[i - 1][1] % mod) % mod;
            dp2[i][0] = (dp2[i - 1][1] % mod + (dp2[i - 1][0] - dp2[i - 3][1] + mod) % mod) % mod;
        }
        dp3[0][1] = dp3[0][0] = dp3[0][2] = 1;
        dp3[1][0] = 3, dp3[1][1] = 3, dp3[1][2] = 2;
        dp3[2][0] = 3 + 2 + 3 - 1, dp3[2][1] = 8, dp3[2][2] = 4;
        for (int i = 1; i < n; i++) {
            dp3[i][2] = (dp2[i - 1][0] % mod + dp2[i - 1][1] % mod) % mod;
        }
        for (int i = 3; i < n; i++) {
            dp3[i][0] = (dp3[i - 1][1] % mod + dp3[i - 1][2] % mod + (dp3[i - 1][0] - (dp3[i - 3][1] + dp3[i - 3][2]) + mod) % mod) % mod;
            dp3[i][1] = (dp3[i - 1][1] % mod + dp3[i - 1][0] % mod + dp3[i - 1][2] % mod) % mod;
        }
        return (dp3[n - 1][0] + dp3[n - 1][1] + dp3[n - 1][2]) % mod;
    }
};
```