LeetCode 题解工作台
学生出勤记录 II
可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符： 'A' ：Absent，缺勤 'L' ：Late，迟到 'P' ：Present，到场 如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励： 按 总出勤 计，学生缺勤（ 'A…
1
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $dfs(i, j, k)$，表示从第 个出勤记录开始，当前缺勤次数为 ，目前最后连续迟到次数为 时，可获得出勤奖励的情况数量。那么答案就是 $dfs(0, 0, 0)$。 函数 $dfs(i, j, k)$ 的执行过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
'A'：Absent，缺勤'L'：Late，迟到'P'：Present，到场
如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
- 按 总出勤 计，学生缺勤（
'A'）严格 少于两天。 - 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（
'L'）记录。
给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 109 + 7 取余 的结果。
示例 1：
输入：n = 2 输出：8 解释： 有 8 种长度为 2 的记录将被视为可奖励： "PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL" 只有"AA"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。
示例 2：
输入：n = 1 输出：3
示例 3：
输入：n = 10101 输出：183236316
提示：
1 <= n <= 105
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示从第 个出勤记录开始，当前缺勤次数为 ，目前最后连续迟到次数为 时，可获得出勤奖励的情况数量。那么答案就是 。
函数 的执行过程如下：
- 如果 ，说明已经遍历完所有出勤记录，返回 ；
- 如果 ，说明当前缺勤次数为 ，那么可以选择缺勤，即 ；
- 如果 ，说明当前连续迟到次数小于 ，那么可以选择迟到，即 ；
- 无论如何，都可以选择到场，即 。
我们将上述三种情况的结果相加，即为 的结果。
为了避免重复计算，我们可以使用记忆化搜索。
时间复杂度 ，空间复杂度 。其中 为出勤记录的长度。
class Solution:
def checkRecord(self, n: int) -> int:
@cache
def dfs(i, j, k):
if i >= n:
return 1
ans = 0
if j == 0:
ans += dfs(i + 1, j + 1, 0)
if k < 2:
ans += dfs(i + 1, j, k + 1)
ans += dfs(i + 1, j, 0)
return ans % mod
mod = 10**9 + 7
ans = dfs(0, 0, 0)
dfs.cache_clear()
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Check if the candidate understands how state transitions work in dynamic programming.
- question_mark
Ensure they are aware of the modulo operation to handle large numbers.
- question_mark
Evaluate their approach to optimizing space complexity in this problem.
常见陷阱
外企场景- error
Not handling the modulo operation properly could lead to incorrect results.
- error
Misunderstanding the state transitions can result in missing valid sequences.
- error
Using excessive space for the DP array instead of optimizing it to O(1).
进阶变体
外企场景- arrow_right_alt
Consider variants where the student can have more than one late arrival, increasing the complexity of the state transitions.
- arrow_right_alt
Modify the problem by changing the number of absences allowed (e.g., 3 absences instead of 1).
- arrow_right_alt
Extend the problem to account for different types of attendance records (e.g., early arrivals, half-day attendance).