LeetCode_动态规划_困难_552.学生出勤记录 II

1.题目

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/student-attendance-record-ii

2.思路

（1）动态规划
思路参考本题官方题解。

① 定义 dp 数组，dp[i][j][k] 表示第 i 天，在缺席了 j 次以及迟到了 k 次的情况下，还可以获得出勤奖励的记录情况数量，需要注意的是由于 dp 数组记录的是可以获得出勤奖励的记录情况数量，所以 j 和 k 有一定的范围限制，其中 0 ≤ j ≤ 1，0 ≤ k ≤ 2；

 int[][][] dp = new int[n + 1][2][3];
1

② 分析状态，dp[i][j][k] 一共有以下 6 种情况：

(1) dp[i][0][0]: 到今天结束为止，总共 0 次缺席，昨天未迟到
(2) dp[i][0][1]: 到今天结束为止，总共 0 次缺席，昨天迟到但前天未迟到
(3) dp[i][0][2]: 到今天结束为止，总共 0 次缺席，昨天、前天均迟到
(4) dp[i][1][0]: 到今天结束为止，总共 1 次缺席，昨天未迟到
(5) dp[i][1][1]: 到今天结束为止，总共 1 次缺席，昨天迟到但前天未迟到
(6) dp[i][1][2]: 到今天结束为止，总共 1 次缺席，昨天、前天均迟到

这里需要注意的是如果学生存在连续 3 天或连续 3 天以上的迟到（'L'）记录，那么就不能获得出勤奖励，这里强调的是记录的连续性，而非总次数。
举例：如果第 i 天迟到了，要想获得出勤奖励，那么昨天、前天不能都迟到，即只有昨天和前天的出勤情况可以影响到今天。
1
2
3
4
5
6
7
8
9

③ 状态转移见下面代码中的注释。

相似题目：551.学生出勤记录 I

3.代码实现（Java）

//思路1————动态规划
class Solution {
    public int checkRecord(int n) {
        int mod = 1000000007;
        // dp[i][j][k] 表示第 i 天，在缺席了 j 次以及迟到了 k 次的情况下，还可以获得出勤奖励的记录情况数量 
        int[][][] dp = new int[n + 1][2][3];
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            //第 i 天以 P 结尾的数量为前一天上述六种情况之和
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    //第 i 天不迟到，之前的迟到记录一笔勾销，所以从 k 从 0 开始记录
                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % mod;
                }
            }
            //第 i 天以 A 结尾的数量为前一天上述第(1)(2)(3)种情况之和
            for (int k = 0; k <= 2; k++) {
                /*
                	第 i 天未迟到但是缺勤：
                	之前的迟到记录一笔勾销，所以从 k 从 0 开始记录
                	第 i - 1 的天的出勤记录（即字符串）中不能有'A'，即其数量为 0
                */
                dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % mod;
            }
            //第 i 天以 L 结尾的数量为前一天上述第(1)(2)(4)(5)种情况之和
            for (int j = 0; j <= 1; j++) {
                for (int k = 1; k <= 2; k++) {
                    //第 i 天迟到，所以第 i 天的 k 的取值为 1 或 2
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % mod;
                }
            }
        }
        int sum = 0;
        //将第 n 天的 6 种情况相加
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum = (sum + dp[n][j][k]) % mod;
            }
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42