题目描述

给定一个正整数 n，返回长度为 n 的所有可被视为可奖励的出勤记录的数量。
答案可能非常大，你只需返回结果模 $10^9 + 7$ 的值。

学生出勤记录是只包含以下三个字符的字符串：

1. 'A' : Absent，缺勤
2. 'L' : Late，迟到
3. 'P' : Present，到场

如果一个学生的出勤纪录中不超过一个'A'(缺勤)并且不超过两个连续的'L'(迟到)，那么这个学生会被奖赏。

样例

输入: n = 2
输出: 8 
解释：
有8个长度为2的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励，因为缺勤次数超过一次。

注意

• n 的值不会超过 100000。

算法

(动态规划) $O(n)$

1. 设计状态 $f(i,j,k)$ 表示已经完成了前 $i$ 次出勤记录，包含 $j$ 个 ‘A‘ 和末尾连续 $k$ 个 ‘L‘ 的方案数。初始时 $f(0,0,0) = 1$。
2. 考虑 $f(i,j,k)$ 能转移到哪些状态。尝试填写第 $i+1$ 次出勤记录，有三种情况：若第 $i+1$ 次出勤记录为 ‘P‘，则 $f(i+1, j, 0) += f(i,j,k)$；若第 $i+1$ 次出勤记录为 ‘L‘，在 $k<2$ 时可以 $f(i+1, j, k+1) += f(i,j,k)$；若第 $i+1$ 次出勤记录为 ‘A‘，在 $j<1$ 时可以 $f(i+1, j+1, 0) += f(i,j,k)$；
3. 最后答案为 $f(n, j, k)$ 的总和。

时间复杂度

• 状态数为 $O(n)$，转移数和转移时间均为 $O(1)$，故总时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    const int MOD = 1000000007;
    int f[100010][2][3];
    int checkRecord(int n) {
        f[0][0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 1; j++)
                for (int k = 0; k <= 2; k++) {
                    f[i + 1][j][0] = (f[i + 1][j][0] + f[i][j][k]) % MOD;
                    if (k < 2)
                        f[i + 1][j][k + 1] = (f[i + 1][j][k + 1] + f[i][j][k]) % MOD;
                    if (j < 1)
                        f[i + 1][j + 1][0] = (f[i + 1][j + 1][0] + f[i][j][k]) % MOD;
                }
        }

        int ans = 0;
        for (int j = 0; j <= 1; j++)
            for (int k = 0; k <= 2; k++)
                ans = (ans + f[n][j][k]) % MOD;
        return ans;
    }
};