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

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