leetcode 552. 学生出勤记录 II

题目描述

可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

• '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

解题思路

方法一：动态规划
可以使用动态规划计算可奖励的出勤记录的数量。

由于可奖励的出勤记录要求缺勤次数少于 2 和连续迟到次数少于 3，因此动态规划的状态由总天数、缺勤次数和结尾连续迟到次数决定（由于不会记录连续迟到次数等于或多于 3 的情况，因此非结尾的连续迟到次数一定少于 3，只需要记录结尾连续迟到次数即可）。

定义 dp[i][j][k] 表示前 i 天有 j 个 ‘A’ 且结尾有连续 k 个 ‘L’ 的可奖励的出勤记录的数量，其中 0≤i≤n，0≤j≤1，0≤k≤2。

当 i=0 时，没有任何出勤记录，此时 ‘A’ 的数量和结尾连续 ‘L’ 的数量一定是 0，因此动态规划的边界情况是 dp[0][0][0]=1。

当 1≤i≤n 时，dp[i][][] 的值从 dp[i−1][][] 的值转移得到，计算每个状态的值需要考虑第 i 天的出勤记录：

如果第 i 天的出勤记录是 ‘P’，则前 i 天和前 i−1 天的出勤记录相比，‘A’ 的数量不变，结尾连续 ‘L’ 的数量清零，因此对 0≤j≤1，有

如果第 i 天的出勤记录是 ‘A’，则前 i 天和前 i−1 天的出勤记录相比，‘A’ 的数量加 1，结尾连续 ‘L’ 的数量清零，此时要求前 i−1 天的出勤记录记录中的 ‘A’ 的数量必须为 0，否则前 i 天的出勤记录至少有 2 个 ‘A’，不满足可奖励的条件，因此有

如果第 i 天的出勤记录是 ‘L’，则前 i 天和前 i−1 天的出勤记录相比，‘A’ 的数量不变，结尾连续 ‘L’ 的数量加 1，此时要求前 i−1 天的出勤记录记录中的结尾连续 ‘L’ 的数量不超过 1，否则前 i 天的出勤记录的结尾至少有 3 个 ‘L’，不满足可奖励的条件，因此对 0≤j≤1 和 1≤k≤2，有

上述状态转移方程对于 i=1 也适用。

计算长度为 n 的所有可奖励的出勤记录的数量，即为计算 dp[n][][] 的所有元素之和。计算过程中需要将结果对 10^9 +7 取模。

根据上述思路，可以得到时间复杂度和空间复杂度都是 O(n) 的实现。

class Solution:def checkRecord(self, n: int) -> int:MOD = 10**9 + 7# 长度，A 的数量，结尾连续 L 的数量dp = [[[0, 0, 0], [0, 0, 0]] for _ in range(n + 1)]dp[0][0][0] = 1for i in range(1, n + 1):# 以 P 结尾的数量for j in range(0, 2):for k in range(0, 3):dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD# 以 A 结尾的数量for k in range(0, 3):dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD# 以 L 结尾的数量for j in range(0, 2):for k in range(1, 3):dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MODtotal = 0for j in range(0, 2):for k in range(0, 3):total += dp[n][j][k]return total % MOD

注意到 dp[i][][] 只会从 dp[i−1][][] 转移得到。因此可以将 dp 中的总天数的维度省略，将空间复杂度优化到 O(1)。

class Solution:def checkRecord(self, n: int) -> int:MOD = 10**9 + 7# A 的数量，结尾连续 L 的数量dp = [[0, 0, 0], [0, 0, 0]]dp[0][0] = 1for i in range(1, n + 1):dpNew = [[0, 0, 0], [0, 0, 0]]# 以 P 结尾的数量for j in range(0, 2):for k in range(0, 3):dpNew[j][0] = (dpNew[j][0] + dp[j][k]) % MOD# 以 A 结尾的数量for k in range(0, 3):dpNew[1][0] = (dpNew[1][0] + dp[0][k]) % MOD# 以 L 结尾的数量for j in range(0, 2):for k in range(1, 3):dpNew[j][k] = (dpNew[j][k] + dp[j][k - 1]) % MODdp = dpNewtotal = 0for j in range(0, 2):for k in range(0, 3):total += dp[j][k]return total % MOD

复杂度分析

时间复杂度：O(n)。动态规划需要计算 n 天的状态，每天的状态有 2×3=6 个，每天的状态需要 O(1) 的时间计算。

空间复杂度：O(1)。使用空间优化的实现，空间复杂度是 O(1)。

方法二：矩阵快速幂
我们还可以使用矩阵快速幂来求解，该方法可以将方法一的时间复杂度由 O(n) 降为 O(logn)。

为了使用矩阵快速幂，需要将方法一的动态规划表示中的 j 和 k 合并到一个维度，即动态规划的状态为：dp[i][j×3+k] 表示前 i 天有 j 个 ‘A’ 且结尾有连续 k 个 ‘L’ 的可奖励的出勤记录的数量，其中 0≤i≤n，0≤j≤1，0≤k≤2，0≤j×3+k<6。

在新的动态规划状态定义下，边界情况是 dp[0][0]=1，当 1≤i≤n 时，状态转移方程如下：

令 dp[n] 表示包含 6 个元素的行向量：

我们可以构建这样一个递推关系：

 
因此：

令：

因此只要我们能快速计算矩阵 M 的 n 次幂，就可以得到 dp[n] 的值，然后计算可奖励的出勤记录的数量。如果直接求取 Mn
 ，时间复杂度是 O(n)，可以定义矩阵乘法，然后用快速幂算法来加速这里 Mn
  的求取。计算过程中需要将结果对 10^9 +7 取模。

class Solution:def checkRecord(self, n: int) -> int:MOD = 10**9 + 7mat = [[1, 1, 0, 1, 0, 0],[1, 0, 1, 1, 0, 0],[1, 0, 0, 1, 0, 0],[0, 0, 0, 1, 1, 0],[0, 0, 0, 1, 0, 1],[0, 0, 0, 1, 0, 0],]def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:rows, columns, temp = len(a), len(b[0]), len(b)c = [[0] * columns for _ in range(rows)]for i in range(rows):for j in range(columns):for k in range(temp):c[i][j] += a[i][k] * b[k][j]c[i][j] %= MODreturn cdef matrixPow(mat: List[List[int]], n: int) -> List[List[int]]:ret = [[1, 0, 0, 0, 0, 0]]while n > 0:if (n & 1) == 1:ret = multiply(ret, mat)n >>= 1mat = multiply(mat, mat)return retres = matrixPow(mat, n)ans = sum(res[0])return ans % MOD