NeetCode #707LC-552Hard1-D Dynamic Programming
← Back to All Problems#707 · #552 · Student Attendance Record II(学生出勤记录 II)
📌 Problem Statement & Constraints
Count the number of attendance records of length
n (each day is A absent, L late, or P present) that contain at most one A and no three consecutive L, modulo 10^9 + 7. Constraints: 1 <= n <= 10^5.💡 Core Algorithmic Approaches
- Track two dimensions of state: how many
Ahave been used (0 or 1) and the length of the current trailing run ofL(0, 1, or 2). - Appending
Presets the trailing run to 0; appendingLincrements it (allowed only while it stays below 2); appendingAresets the run and is allowed only when noAhas been used. - Roll a 2x3 table forward one day at a time, keeping constant work per day.
- The answer is the sum over all six states after
ndays.
💻 Benchmark Python3 Implementation
class Solution:
def checkRecord(self, n: int) -> int:
MOD = 10 ** 9 + 7
# dp[a][l]: a = number of A used (0 or 1), l = trailing L count (0,1,2)
dp = [[0] * 3 for _ in range(2)]
dp[0][0] = 1 # empty record
for _ in range(n):
ndp = [[0] * 3 for _ in range(2)]
for a in range(2):
for l in range(3):
v = dp[a][l]
if not v:
continue
ndp[a][0] = (ndp[a][0] + v) % MOD # append P
if a == 0:
ndp[1][0] = (ndp[1][0] + v) % MOD # append A
if l < 2:
ndp[a][l + 1] = (ndp[a][l + 1] + v) % MOD # append L
dp = ndp
return sum(dp[a][l] for a in range(2) for l in range(3)) % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): constant work per day across six states.
💾 Space Complexity
O(1): two 2x3 tables.
⚠️ Interview Pitfalls & Follow-ups
- Allowing two or more
As: the absent count is capped at one, which theadimension enforces. - Tracking only the last character: three consecutive
Ls must be excluded, so the trailing-Lrun length is part of the state. - Seeding
dp[0][0] = 1incorrectly: the empty record has zeroAs and zero trailingLs. - Summing only the no-
Astates: records with exactly oneAalso count, so all six states are summed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.