LeetCode 552. 学生出勤记录 II
题目描述
题意分析
记录由缺勤
A、迟到L、到场P组成，要求长度为n，总共至多出现一个A，并且不能出现连续三个L。统计所有满足条件的记录数量，对10^9+7取模。
解法：缺勤次数与末尾迟到长度的滚动 DP
核心思路
[!blue]
处理完若干天后，定义
dp[a][l]为合法记录中“缺勤总数为a，末尾连续迟到长度为l”的数量。合法范围只有a=0,1和l=0,1,2，一共六种状态。这两个量足以决定下一天的选择。缺勤限制涉及整个历史，所以要保存
A的总数；连续迟到只可能在末尾继续延长，较早的迟到段已经通过合法性检查，不必再记录。对当前状态追加
P，缺勤数不变，末尾迟到归零，转到next[a][0]。只有a=0时可以追加A，转到next[1][0]；只有l<2时可以追加L，转到next[a][l+1]。每个合法选择都把当前状态的记录数累加到对应下一状态。任意合法记录去掉最后一个字符后，必然是上一天的某条合法记录；它的末字符又唯一确定了本次转移。因此这些转移覆盖全部合法记录，也不会重复计数。每轮使用新的
next，保证所有来源都属于同一天，避免刚生成的状态被再次扩展。
解题步骤
- 初始化
dp[0][0]=1，表示长度为 0 的空记录；其余状态为 0。- 每天先创建全零的
next，遍历六种状态，按规则尝试追加P、A、L。- 每次累加立即取模，完成一天后令
dp=next。- 完成
n天后，将六种状态的数量相加并取模，因为它们全都满足奖励条件，结尾字符没有额外限制。
P和A都会打断连续迟到，但只有A增加缺勤总数。即使两个A之间隔着其他字符，第二次缺勤仍然必须被禁止。
代码实现
class Solution {
public int checkRecord(int n) {
int mod = 1_000_000_007;
int[][] dp = new int[2][3];
dp[0][0] = 1;
for (int day = 0; day < n; day++) {
int[][] next = new int[2][3];
for (int a = 0; a < 2; a++) {
for (int l = 0; l < 3; l++) {
int count = dp[a][l];
next[a][0] = (next[a][0] + count) % mod;
if (a == 0) {
next[1][0] = (next[1][0] + count) % mod;
}
if (l < 2) {
next[a][l + 1] = (next[a][l + 1] + count) % mod;
}
}
}
dp = next;
}
int answer = 0;
for (int[] row : dp) {
for (int count : row) {
answer = (answer + count) % mod;
}
}
return answer;
}
}
func checkRecord(n int) int {
const mod = 1000000007
dp := [2][3]int{}
dp[0][0] = 1
for day := 0; day < n; day++ {
next := [2][3]int{}
for a := 0; a < 2; a++ {
for l := 0; l < 3; l++ {
count := dp[a][l]
next[a][0] = (next[a][0] + count) % mod
if a == 0 {
next[1][0] = (next[1][0] + count) % mod
}
if l < 2 {
next[a][l+1] = (next[a][l+1] + count) % mod
}
}
}
dp = next
}
answer := 0
for _, row := range dp {
for _, count := range row {
answer = (answer + count) % mod
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，每天只处理六种状态，每种最多尝试三个转移。
- 空间复杂度：$O(1)$，只保留当前与下一天的两张六状态表。每次相加的两个数都小于模数，和最多为
2×(1000000007-1)，不会超过 32 位有符号整数范围。
关键点总结
[!green]
a保存累计缺勤次数，l保存末尾连续迟到长度，二者的统计范围不同。- 相同状态的历史记录具有相同的后续选择，可以合并为一个计数。
- 转移只读取旧表，所有新增记录写入新表，处理完一天再替换。
易错点总结
[!yellow]
- P 或 A 都会打断连续迟到，下一状态的 L 长度必须归零。
- A 不能只统计连续次数，分隔出现的两个 A 同样非法。
- 最终应累加全部六种合法状态，不能只统计某一种结尾。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 551. 学生出勤记录 I | 简单 | 同样限制缺勤总数与连续迟到；原题验证一个字符串，本题把验证状态扩展为所有合法字符串的计数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！