Kimi LeetCode 552.学生出勒记录|| public int checkRecord(int n)

我来为你详细解析 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)
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 代码实现

classSolution{privatestaticfinalintMOD=1_000_000_007;publicintcheckRecord(intn){// dp[j][k]: j表示缺勤次数(0或1), k表示末尾连续L的次数(0,1,2)// 使用滚动数组优化空间long[][]dp=newlong[2][3];// 初始状态：空字符串，0次缺勤，0个连续Ldp[0][0]=1;for(inti=0;i<n;i++){long[][]newDp=newlong[2][3];for(intj=0;j<=1;j++){// 缺勤次数for(intk=0;k<=2;k++){// 连续L次数longval=dp[j][k];if(val==0)continue;// 1. 添加 P (出席): 重置连续L，缺勤次数不变newDp[j][0]=(newDp[j][0]+val)%MOD;// 2. 添加 A (缺勤): 只能在没有缺勤过时添加，重置连续Lif(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;}// 统计所有合法状态longans=0;for(intj=0;j<=1;j++){for(intk=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) 的版本即可。