问题描述
可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
'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
代码
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;
}
};