LC 552. 学生出勤记录 II

题目描述

这是 LeetCode 上的 552. 学生出勤记录 II ,难度为 困难

可以用字符串表示一个学生的出勤记录,其中的每个字符用来标记当天的出勤情况(缺勤、迟到、到场)。

记录中只含下面三种字符:

  • ‘A’:Absent,缺勤
  • ‘L’:Late,迟到
  • ‘P’:Present,到场

如果学生能够同时满足下面两个条件,则可以获得出勤奖励:

  • 总出勤计,学生缺勤(’A’)严格 少于两天。
  • 学生不会存在 连续 3 天或 连续 3 天以上的迟到(’L’)记录。

给你一个整数 n ,表示出勤记录的长度(次数)。请你返回记录长度为 n 时,可能获得出勤奖励的记录情况 数量 。

答案可能很大,所以返回对 $10^9 + 7$ 取余的结果。

示例 1:

1
2
3
4
5
6
7
8
输入:n = 2

输出:8

解释:
8 种长度为 2 的记录将被视为可奖励:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励,因为缺勤次数为 2 次(需要少于 2 次)。

示例 2:
1
2
3
输入:n = 1

输出:3

示例 3:
1
2
3
输入:n = 10101

输出:183236316

提示:

  • 1 <= n <= $10^5$

基本分析

根据题意,我们知道一个合法的方案中 A 的总出现次数最多为 $1$ 次,L 的连续出现次数最多为 $2$ 次。

因此在枚举/统计合法方案的个数时,当我们决策到某一位应该选什么时,我们关心的是当前方案中已经出现了多少个 A(以决策当前能否填入 A)以及连续出现的 L 的次数是多少(以决策当前能否填入 L)。


记忆化搜索

枚举所有方案的爆搜 DFS 代码不难写,大致的函数签名设计如下:

1
2
3
4
5
6
7
8
/**
* @param u 当前还剩下多少位需要决策
* @param acnt 当前方案中 A 的总出现次数
* @param lcnt 当前方案中结尾 L 的连续出现次数
* @param cur 当前方案
* @param ans 结果集
*/
void dfs(int u, int acnt, int lcnt, String cur, List<String> ans);

实际上,我们不需要枚举所有的方案数,因此我们只需要保留函数签名中的前三个参数即可。

同时由于我们在计算某个 $(u, acnt, lcnt)$ 的方案数时,其依赖的状态可能会被重复使用,考虑加入记忆化,将结果缓存起来。

根据题意,$n$ 的取值范围为 $[0, n]$,$acnt$ 取值范围为 $[0,1]$,$lcnt$ 取值范围为 $[0, 2]$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
int mod = (int)1e9+7;
int[][][] cache;
public int checkRecord(int n) {
cache = new int[n + 1][2][3];
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 3; k++) {
cache[i][j][k] = -1;
}
}
}
return dfs(n, 0, 0);
}
int dfs(int u, int acnt, int lcnt) {
if (acnt >= 2) return 0;
if (lcnt >= 3) return 0;
if (u == 0) return 1;
if (cache[u][acnt][lcnt] != -1) return cache[u][acnt][lcnt];
int ans = 0;
ans = dfs(u - 1, acnt + 1, 0) % mod; // A
ans = (ans + dfs(u - 1, acnt, lcnt + 1)) % mod; // L
ans = (ans + dfs(u - 1, acnt, 0)) % mod; // P
cache[u][acnt][lcnt] = ans;
return ans;
}
}

  • 时间复杂度:有 $O(n 2 3)$ 个状态需要被计算,复杂度为 $O(n)$
  • 空间复杂度:$O(n)$

状态机 DP

通过记忆化搜索的分析我们发现,当我们在决策下一位是什么的时候,依赖于前面已经填入的 A 的个数以及当前结尾处的 L 的连续出现次数。

也就说是,状态 $f[u][acnt][lcnt]$ 必然被某些特定状态所更新,或者说由 $f[u][[acnt][lcnt]$ 出发,所能更新的状态是固定的。

因此这其实是一个状态机模型的 DP 问题。

根据「更新 $f[u][acnt][lcnt]$ 需要哪些状态值」还是「从 $f[u][acnt][lcnt]$ 出发,能够更新哪些状态」,我们能够写出两种方式(方向)的 DP 代码:

一类是从 $f[u][acnt][lcnt]$ 往回找所依赖的状态;一类是从 $f[u][acnt][lcnt]$ 出发往前去更新所能更新的状态值。

无论是何种方式(方向)的 DP 实现都只需搞清楚「当前位的选择对 $acnt$​ 和 $lcnt$​ 的影响」即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 从 f[u][acnt][lcnt] 往回找所依赖的状态
class Solution {
int mod = (int)1e9+7;
public int checkRecord(int n) {
int[][][] f = new int[n + 1][2][3];
f[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 3; k++) {
if (j == 1 && k == 0) { // A
f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][0]) % mod;
f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][1]) % mod;
f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][2]) % mod;
}
if (k != 0) { // L
f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - 1]) % mod;
}
if (k == 0) { // P
f[i][j][k] = (f[i][j][k] + f[i - 1][j][0]) % mod;
f[i][j][k] = (f[i][j][k] + f[i - 1][j][1]) % mod;
f[i][j][k] = (f[i][j][k] + f[i - 1][j][2]) % mod;
}
}
}
}
int ans = 0;
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 3; k++) {
ans += f[n][j][k];
ans %= mod;
}
}
return ans;
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 从 f[u][acnt][lcnt] 出发往前去更新所能更新的状态值
class Solution {
int mod = (int)1e9+7;
public int checkRecord(int n) {
int[][][] f = new int[n + 1][2][3];
f[0][0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 3; k++) {
if (j != 1) f[i + 1][j + 1][0] = (f[i + 1][j + 1][0] + f[i][j][k]) % mod; // A
if (k != 2) f[i + 1][j][k + 1] = (f[i + 1][j][k + 1] + f[i][j][k]) % mod; // L
f[i + 1][j][0] = (f[i + 1][j][0] + f[i][j][k]) % mod; // P
}
}
}
int ans = 0;
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 3; k++) {
ans += f[n][j][k];
ans %= mod;
}
}
return ans;
}
}
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$

矩阵快速幂

之所以在动态规划解法中强调更新状态的方式(方向)是「往回」还是「往前」,是因为对于存在线性关系(同时又具有结合律)的递推式,我们能够通过「矩阵快速幂」来进行加速。

矩阵快速幂的基本分析之前在 (题解) 1137. 第 N 个泰波那契数 详细讲过。

由于 $acnt$ 和 $lcnt$ 的取值范围都很小,其组合的状态只有 $2 3 = 6$ 种,我们使用 $idx = acnt 3 + lcnt$ 来代指组合(通用的二维转一维方式):

  • $idx = 0$ :$acnt = 0、lcnt = 0$;
  • $idx = 1$ :$acnt = 1、lcnt = 0$;
  • $idx = 5$ :$acnt = 1、lcnt = 2$;

最终答案为 $ans = \sum_{idx = 0}^{5} f[n][idx]$​,将答案依赖的状态整理成列向量:

根据状态机逻辑,可得:

我们令:

根据「矩阵乘法」即有:

起始时,我们只有 $g[0]$,根据递推式得:

再根据矩阵乘法具有「结合律」,最终可得:

计算 $mat^n$ 可以套用「快速幂」进行求解。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
int N = 6;
int mod = (int)1e9+7;
long[][] mul(long[][] a, long[][] b) {
int r = a.length, c = b[0].length, z = b.length;
long[][] ans = new long[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
for (int k = 0; k < z; k++) {
ans[i][j] += a[i][k] * b[k][j];
ans[i][j] %= mod;
}
}
}
return ans;
}
public int checkRecord(int n) {
long[][] ans = new long[][]{
{1}, {0}, {0}, {0}, {0}, {0}
};
long[][] mat = new long[][]{
{1, 1, 1, 0, 0, 0},
{1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0},
{1, 1, 1, 1, 1, 1},
{0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0}
};
while (n != 0) {
if ((n & 1) != 0) ans = mul(mat, ans);
mat = mul(mat, mat);
n >>= 1;
}
int res = 0;
for (int i = 0; i < N; i++) {
res += ans[i][0];
res %= mod;
}
return res;
}
}

  • 时间复杂度:$O(\log{n})$
  • 空间复杂度:$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.552 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。