我来为你详细解析 LeetCode 552. 学生出勤记录 II 这道动态规划题目。
题目分析
出勤记录规则：
- P (Present)：出席
- A (Absent)：缺勤
- L (Late)：迟到
奖励条件：
求长度为 n 的可奖励出勤记录的数量，结果对 10^9 + 7 取模。
状态设计
我们需要跟踪两个维度：
- 缺勤次数：0 次或 1 次
- 末尾连续迟到次数：0、1 或 2 次
状态定义： dp[i][j][k] 表示长度为 i 的记录中，缺勤 j 次（0 或 1），且末尾有连续 k 个 L（0、1、2）的可奖励记录数。
状态转移
对于每个位置，我们可以选择 P、A 或 L：
当前选择转移条件新状态
P无限制dp[i][j][0] += dp[i-1][j][k] (k=0,1,2)
Aj < 1dp[i][1][0] += dp[i-1][0][k] (k=0,1,2)
Lk < 2dp[i][j][k+1] += dp[i-1][j][k]
Java 代码实现
class Solution {
private static final int MOD = 1_000_000_007;
public int checkRecord(int n) {
// dp[j][k]: j表示缺勤次数(0或1), k表示末尾连续L的次数(0,1,2)
// 使用滚动数组优化空间
long[][] dp = new long[2][3];
// 初始状态：空字符串，0次缺勤，0个连续L
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
long[][] newDp = new long[2][3];
for (int j = 0; j <= 1; j++) { // 缺勤次数
for (int k = 0; k <= 2; k++) { // 连续L次数
long val = dp[j][k];
if (val == 0) continue;
// 1. 添加 P (出席): 重置连续L，缺勤次数不变
newDp[j][0] = (newDp[j][0] + val) % MOD;
// 2. 添加 A (缺勤): 只能在没有缺勤过时添加，重置连续L
if (j == 0) {
newDp[1][0] = (newDp[1][0] + val) % MOD;
}
// 3. 添加 L (迟到): 连续L次数+1，缺勤次数不变
if (k < 2) {
newDp[j][k + 1] = (newDp[j][k + 1] + val) % MOD;
}
}
}
dp = newDp;
}
// 统计所有合法状态
long ans = 0;
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
ans = (ans + dp[j][k]) % MOD;
}
}
return (int) ans;
}
}
复杂度分析
- 时间复杂度： O(n)，需要遍历 n 个位置，每个位置处理常数个状态（2×3=6 个）
- 空间复杂度： O(1)，使用滚动数组，只保留两层状态
示例验证
-
n = 2 时，答案为 8
- 所有可能：PP, PA, PL, AP, AA, AL, LP, LA, LL
- 排除 AA（2次缺勤），剩余 8 个
-
n = 10101 时，答案为 183236316
优化版本（矩阵快速幂）
对于极大的 n，可以使用矩阵快速幂将时间优化到 O(\\log n)。由于状态只有 6 个（2×3），可以构建 6×6 的转移矩阵，但这通常作为进阶优化，面试中先写出 O(n) 的版本即可。
