「力扣」第 552 题：学生出勤记录 II（困难）
- 题目链接：学生出勤记录 II
可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
-
'A'：Absent，缺勤 -
'L'：Late，迟到 -
'P'：Present，到场
如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
- 按 总出勤 计，学生缺勤（
'A'）严格 少于两天。 - 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（
'L'）记录。
给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 10^9 + 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^5
状态转移方程看得我头皮发麻。在纸上把所有情况枚举了一遍才弄懂：
输入 n 代表的是天数，我每天去上学，有三种结果：准时 P，缺席 P，迟到 L。如果我 n 天后没有缺席超过一次（严格少于 2 天），且没有连续超过两天迟到，则我可以拿到奖励。
我在 1 - n 中的任何一天，是否有可能拿到奖励，取决于我过去的日子的上学情况，例如：
- 例 1：如果今天缺席了，而我过去某一天也缺席了，则我一定无法最终拿到奖励；
- 例 2：如果今天缺席了，我过去每一天都是好学生，一次缺席也没有，一次迟到也没有，那我今天缺席一次没啥嘛，之后好好表现还是有可能拿到奖励。
这样就是从小问题可以推导出大问题，用动态规划解。
dp[i][j][k] 等于第 i 天，在过去缺席了 j 次，以及连续迟到了 k 次的情况下，还可以拿到奖励的出席排列的数量。随着天数的增加，这个 dp 的值肯定是递减的，因为搞不好未来哪一天就缺席或者迟到再也拿不到奖励了。
j 一共有两种可能，0 或者 1 ，对应不能缺席超过 1 次。k 一共有三种可能：0,1,2，对应不能连续迟到超过 2 次。
今天：缺席、不缺席、连续迟到天数
dp[天数][缺席][连续迟到] 一共有六种：
dp[i][0][0]：今天截止 0 次缺席，今天截止 0 天连续迟到。
dp[i][0][1]：今天截止 0 次缺席，今天截止 1 天连续迟到。
dp[i][0][2]：今天截止 0 次缺席，今天截止 2 天连续迟到。
dp[i][1][0]：今天截止 1 次缺席，今天截止 0 天连续迟到。
dp[i][1][1]：今天截止 1 次缺席，今天截止 1 天连续迟到。
dp[i][1][2]：今天截止 1 次缺席，今天截止 2 天连续迟到。
我们依次分析六种情况：
情况 1：今天截止 0 次缺席，今天截止 0 次连续迟到：
dp[i][0][0] = dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]
说明：「今天截止 0 次缺席」说明今天出席。
- 过去一定也是
0次缺席，但过去可以有0，1，2次连续迟到； - 只要今天按时出席，过去的迟到记录都一笔勾销。
情况 2：今天截止 1 次缺席，今天截止 0 次连续迟到：
dp[i][1][0] = dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2] + dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]
分两种情况：
- 前三项，代表过去有 1 次缺席，今天没有缺席，但过去可以有 0、1、2 次连续迟到，过去的迟到记录都一笔勾销。
- 后三项，代表过去有 0 次缺席，今天缺席了，但过去可以有 0、1、2 次连续迟到，过去的迟到记录都一笔勾销。
情况 3：今天截止 0 次缺席，今天截止 1 次连续迟到：
dp[i][0][1] = dp[i - 1][0][0];
过去 0 次缺席，过去 0 次迟到，今天迟到了。
情况 4：今天截止 0 次缺席，今天截止 2 次连续迟到：
dp[i][0][2] = dp[i - 1][0][1];
过去 0 次缺席，昨天迟到，今天迟到了，（只能从 1 转来）。
情况 5：今天截止 1 次缺席，今天截止 1 次连续迟到：
dp[i][1][1] = dp[i - 1][1][0];
过去 1 次缺席，过去 0 次迟到，今天迟到了。
这里可以仔细想一下，我今天必须要迟到，所以今天截止的 1 次缺席必定来自过去。
情况 6：今天截止 1 次缺席，今天截止 2 次连续迟到：
dp[i][1][2] = dp[i - 1][1][1];
过去 1 次缺席，昨天迟到，今天迟到了。
最后，把最后一天的六种情况加和即为答案。
class Solution {
public int checkRecord(int n) {
final int MOD = 1000000007;
int[][][] dp = new int[n + 1][2][3]; // 长度，A （缺席）的数量，结尾连续 L （迟到）的数量
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
// 以 P 结尾的数量
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD;
}
}
// 以 A 结尾的数量
for (int k = 0; k <= 2; k++) {
dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD;
}
// 以 L 结尾的数量
for (int j = 0; j <= 1; j++) {
for (int k = 1; k <= 2; k++) {
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;
}
}
}
int sum = 0;
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
sum = (sum + dp[n][j][k]) % MOD;
}
}
return sum;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/student-attendance-record-ii/solution/xue-sheng-chu-qin-ji-lu-ii-by-leetcode-s-kdlm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
