Hard

题目描述

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

  • ‘A’：缺勤
  • ‘L’：迟到
  • ‘P’：到场

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

  • 按总出勤计，学生缺勤（‘A’）严格少于 2 天。
  • 学生不会存在连续 3 天或连续 3 天以上的迟到（‘L’）记录。

给你一个整数 n，请返回记录长度为 n 时，可能获得出勤奖励的记录情况数量。答案可能很大，所以返回对 10^9 + 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^5

解题思路

这道题是一个典型的动态规划问题，需要考虑两个约束条件：

  1. 缺勤（‘A’）次数严格少于 2 次（即最多 1 次）
  2. 不能有连续 3 次或以上的迟到（‘L’）

我们可以用状态来表示当前的情况：

  • 状态定义：dp[i][j][k] 表示长度为 i 的字符串，包含 j 次缺勤，结尾连续 k 次迟到的方案数
  • 其中：j ∈ {0, 1}，k ∈ {0, 1, 2}（连续迟到次数最多为 2）

状态转移方程：

  1. 添加 ‘P’：dp[i][j][0] += dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2]
  2. 添加 ‘A’：dp[i][1][0] += dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]（只有之前没有缺勤才能添加）
  3. 添加 ‘L’：dp[i][j][1] += dp[i-1][j][0]，dp[i][j][2] += dp[i-1][j][1]

为了节省空间，我们可以用滚动数组优化，只保存当前状态。

推荐解法：动态规划 + 状态压缩，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    int checkRecord(int n) {
        const int MOD = 1e9 + 7;
        
        // dp[j][k] 表示包含j次缺勤，结尾连续k次迟到的方案数
        vector<vector<long long>> dp(2, vector<long long>(3, 0));
        dp[0][0] = 1; // 初始状态：0次缺勤，0次连续迟到
        
        for (int i = 0; i < n; i++) {
            vector<vector<long long>> next(2, vector<long long>(3, 0));
            
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    // 添加 'P'
                    next[j][0] = (next[j][0] + dp[j][k]) % MOD;
                    
                    // 添加 'A'（只有之前没有缺勤才能添加）
                    if (j == 0) {
                        next[1][0] = (next[1][0] + dp[j][k]) % MOD;
                    }
                    
                    // 添加 'L'
                    if (k < 2) {
                        next[j][k + 1] = (next[j][k + 1] + dp[j][k]) % MOD;
                    }
                }
            }
            dp = next;
        }
        
        long long result = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                result = (result + dp[j][k]) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # dp[j][k] 表示包含j次缺勤，结尾连续k次迟到的方案数
        dp = [[0] * 3 for _ in range(2)]
        dp[0][0] = 1  # 初始状态：0次缺勤，0次连续迟到
        
        for i in range(n):
            next_dp = [[0] * 3 for _ in range(2)]
            
            for j in range(2):
                for k in range(3):
                    # 添加 'P'
                    next_dp[j][0] = (next_dp[j][0] + dp[j][k]) % MOD
                    
                    # 添加 'A'（只有之前没有缺勤才能添加）
                    if j == 0:
                        next_dp[1][0] = (next_dp[1][0] + dp[j][k]) % MOD
                    
                    # 添加 'L'
                    if k < 2:
                        next_dp[j][k + 1] = (next_dp[j][k + 1] + dp[j][k]) % MOD
            
            dp = next_dp
        
        result = 0
        for j in range(2):
            for k in range(3):
                result = (result + dp[j][k]) % MOD
        
        return result

public class Solution {
    public int CheckRecord(int n) {
        const int MOD = 1000000007;
        
        // dp[j][k] 表示包含j次缺勤，结尾连续k次迟到的方案数
        long[,] dp = new long[2, 3];
        dp[0, 0] = 1; // 初始状态：0次缺勤，0次连续迟到
        
        for (int i = 0; i < n; i++) {
            long[,] next = new long[2, 3];
            
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    // 添加 'P'
                    next[j, 0] = (next[j, 0] + dp[j, k]) % MOD;
                    
                    // 添加 'A'（只有之前没有缺勤才能添加）
                    if (j == 0) {
                        next[1, 0] = (next[1, 0] + dp[j, k]) % MOD;
                    }
                    
                    // 添加 'L'
                    if (k < 2) {
                        next[j, k + 1] = (next[j, k + 1] + dp[j, k]) % MOD;
                    }
                }
            }
            dp = next;
        }
        
        long result = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                result = (result + dp[j, k]) % MOD;
            }
        }
        
        return (int)result;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var checkRecord = function(n) {
    const MOD = 1000000007;
    
    // dp[i][j][k] = number of valid records of length i
    // j = number of A's (0 or 1)
    // k = number of consecutive L's at the end (0, 1, or 2)
    const dp = Array(n + 1).fill().map(() => 
        Array(2).fill().map(() => Array(3).fill(0))
    );
    
    dp[0][0][0] = 1;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < 2; j++) {
            for (let k = 0; k < 3; k++) {
                if (dp[i][j][k] === 0) continue;
                
                // Add P
                dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][k]) % MOD;
                
                // Add A (only if j === 0)
                if (j === 0) {
                    dp[i + 1][1][0] = (dp[i + 1][1][0] + dp[i][j][k]) % MOD;
                }
                
                // Add L (only if k < 2)
                if (k < 2) {
                    dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % MOD;
                }
            }
        }
    }
    
    let result = 0;
    for (let j = 0; j < 2; j++) {
        for (let k = 0; k < 3; k++) {
            result = (result + dp[n][j][k]) % MOD;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)需要遍历 n 天，每天的状态转移是常数时间
空间复杂度O(1)使用固定大小的二维数组存储状态

相关题目