1.题目基本信息

1.1.题目描述

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

• 'A'：Absent，缺勤

• 'L'：Late，迟到

• 'P'：Present，到场

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

• 按 总出勤 计，学生缺勤（'A'）严格 少于两天。

• 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。

给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 109 + 7 取余 的结果。

1.2.题目地址

https://leetcode.cn/problems/student-attendance-record-ii/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

第一步，状态定义。dp[i][j][k]表示长度为i，其中有j个'A'，并以连续k个'L'结尾的出勤记录中，能够得到出勤奖的总情况数。（其中0<=j<=1且0<=k<=2）

第二步，状态初始化。dp[0][0][0]=1

第三步，状态转移。如果第i个字符为'P'，则dp[i][j][0]=sum(dp[i-1][j][k] for k in range(0,3))；如果第i个字符为'A'，dp[i][1][0]=sum(dp[i-1][0][k] for k in range(0,3))；如果第i个字符为'L'，则dp[i][j][k]=dp[i][j][k-1]

第四步，sum(dp[n])即为题解

3.解题代码

python代码

class Solution:
    def checkRecord(self, n: int) -> int:
        # 思路：动态规划
        MOD = 10 ** 9 + 7
        # 第一步，状态定义。dp[i][j][k]表示长度为i，其中有j个'A'，并以连续k个'L'结尾的出勤记录中，能够得到出勤奖的总情况数。（其中0<=j<=1且0<=k<=2）
        dp = [[[0] * 3 for _ in range(2)] for _ in range(n + 1)]
        # 第二步，状态初始化。dp[0][0][0]=1
        dp[0][0][0] = 1
        # 第三步，状态转移。如果第i个字符为'P'，则dp[i][j][0]=sum(dp[i-1][j][k] for k in range(0,3))；如果第i个字符为'A'，dp[i][1][0]=sum(dp[i-1][0][k] for k in range(0,3))；如果第i个字符为'L'，则dp[i][j][k]=dp[i][j][k-1]
        for i in range(1, n + 1):
            for j in range(2):
                for k in range(3):
                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD
            for k in range(3):
                dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD
            for j in range(2):
                for k in range(1, 3):
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD
        # 第四步，sum(dp[n])即为题解
        result = 0
        for j in range(2):
            for k in range(3):
                result = (result + dp[n][j][k]) % MOD
        return result

c++代码

const int MOD = 1e9 + 7;

class Solution {
public:
    int checkRecord(int n) {
        vector<vector<vector<int>>> dp(n + 1, vector(2, vector(3, 0)));
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD;
                }
            }
            for (int k = 0; k <= 2; k++) {
                dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD;
            }
            for (int j = 0; j <= 1; j++) {
                for (int k = 1; k <= 2; k++) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;
                }
            }
        }
        int result = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                result = (result + dp[n][j][k]) % MOD;
            }
        }
        return result;
    }
};

4.执行结果