力扣每日一题2021-08-18学生出勤记录II

552.学生出勤记录II

题目描述

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

• ‘A’：Absent，缺勤
• ‘L’：Late，迟到
• ‘P’：Present，到场
  如果学生能够同时满足下面两个条件，则可以获得出勤奖励：
• 按总出勤记，学生缺勤（‘A’）严格少于两天。
• 学生不会存在连续3天或3天以上的迟到（‘L’）的记录。
  给你一个整数n，表示出勤记录的长度（次数）。请你返回记录长度为n时，可能获得出勤奖励的记录情况数量。答案可能很大，所以返回对10⁹+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 <= 10⁵

思路：动态规划

动态规划

使用动态规划计算可奖励的出勤记录的数量。
由于可奖励的出勤记录要求缺勤次数少于2和连续迟到次数少于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’数量清零。
  $$dp[i][j][0]=dp[i][j][0]+\sum _{k=0}^{2}dp[i-1][j][k]$$
• 如果第i天记录是’A’，则前i天和前i-1天的出勤记录相比，'A’数量加一，结尾连续的’L’数量清零。
  $$dp[i][1][0]=dp[i][1][0]+\sum _{k=0}^{2}dp[i-1][0][k]$$
• 如果第i天记录是’L’，则前i天和前i-1天的出勤记录相比，‘A’数量不变，结尾连续的’L’数量加一，这种情况要求前i-1天的出勤记录的结尾连续’L’的数量不超过2，否则前i天出勤记录结尾将会有3个’L’，不满足条件，因此对于0<=j<=1和1<=k<=2
  $$dp[i][j][k]=dp[i][j][k]+dp[i-1][j][k-1]$$
  这些状态转移方程对于i=1同样适用。
  计算长度为n的所有可奖励的出勤记录的数量，即计算dp[n][][]的所有元素之和。计算结果要对10⁹+7取余。

class Solution:def checkRecord(self, n: int) -> int:mod = 10**9+7# 构建dpdp = [[[0, 0, 0] for i in range(2)] for i in range(n+1)]dp[0][0][0] = 1# 循环计算for 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]# 以A结尾的数量for k in range(0, 3):dp[i][1][0] = dp[i][1][0] + dp[i-1][0][k]# 以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]total = 0for j in range(0, 2):for k in range(0, 3):total += dp[n][j][k]return total%mod

运行后，在计算n=100000时超时了，经过对代码的分析，需要对思路进行调整，不再是只在最后结果取余，而是在过程中每一个状态转移方程都取余。

class Solution:def checkRecord(self, n: int) -> int:mod = 10**9+7# 构建dpdp = [[[0, 0, 0] for i in range(2)] for i in range(n+1)]dp[0][0][0] = 1# 循环计算for 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][][]得到，所以可以将总天数的维度省略进行优化。这里就不再赘述。