0552. Student Attendance Record II
==================================
题目信息
--------
:题号: 0552
:难度: Hard
:主题: 出勤记录计数、长度固定、缺席上限、连续迟到、取模
:原题: `LeetCode 0552 `_
:重点: 统计所有长度为 n 的合法字符串、A 最多一个、不能含 LLL、答案对 10^9+7 取模
题目重述
--------
给定正整数 ``n``,统计长度恰好为 ``n`` 的出勤记录字符串数量。每个位置可以是 ``'A'``、``'L'`` 或 ``'P'``,但合法记录必须同时满足:整个字符串中至多出现一次 ``A``;任何位置都不能出现连续三个 ``L``。
返回合法记录数量对 ``1,000,000,007`` 取模后的结果。不同字符串按字符序列区分;这是统计所有可能记录,而不是判断某一条已给定记录。
自建示例
--------
长度为一:
.. code-block:: text
输入:n = 1
输出:3
解释:"A"、"L"、"P" 三种记录都合法。
长度为二:
.. code-block:: text
输入:n = 2
输出:8
解释:共有 9 个字符串,只有 "AA" 因出现两次缺席而不合法;长度 2 不可能含有 LLL。
状态记录缺席数和连续迟到数
--------------------------
构造记录时,合法性的未来只取决于已经使用了几次 ``A``(0 或 1)以及末尾连续 ``L`` 的长度(0、1 或 2)。在每个状态后追加 ``P``、``A`` 或 ``L``,若不违反限制就把方案数转移到新状态,并按模数保存。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int checkRecord(int n) {
const int mod = 1000000007;
std::array, 2> dp{};
dp[0][0] = 1;
for (int day = 0; day < n; ++day) {
std::array, 2> next{};
for (int absent = 0; absent <= 1; ++absent) {
for (int late = 0; late <= 2; ++late) {
long long ways = dp[absent][late];
if (ways == 0) continue;
next[absent][0] =
(next[absent][0] + ways) % mod; // P
if (absent == 0) {
next[1][0] = (next[1][0] + ways) % mod; // A
}
if (late < 2) {
next[absent][late + 1] =
(next[absent][late + 1] + ways) % mod;
}
}
}
dp = next;
}
long long answer = 0;
for (const auto& row : dp) {
for (long long ways : row) answer = (answer + ways) % mod;
}
return static_cast(answer);
}
};
代码分析
--------
状态中的两个维度正好保存追加字符所需的历史信息,所有合法记录都沿唯一字符序列转移到某个终态,非法的第二个 ``A`` 或第三个连续 ``L`` 不进入状态。状态数固定为 6,每天处理常数转移,时间复杂度为 ``O(n)``,空间复杂度为 ``O(1)``。