我来为你详细解析 LeetCode 552. 学生出勤记录 II 这道动态规划题目。

题目分析

出勤记录规则：

• P (Present)：出席
• A (Absent)：缺勤
• L (Late)：迟到

奖励条件：

1. 缺勤次数 严格少于 2 次（即 A 的个数 ≤ 1）
2. 没有 连续 3 天或以上的迟到（即不能有 LLL）

求长度为 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)
A j < 1 dp[i][1][0] += dp[i-1][0][k] (k=0,1,2)
L k < 2 dp[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) 的版本即可。