日期: 2024 年 8 月 19 日

552.学生出勤记录II

目标

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

  • 'A'：Absent，缺勤
  • 'L'：Late，迟到
  • 'P'：Present，到场

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

  • 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
  • 学生 不会 存在 连续 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

思路

使用 A L P 三种字符组成长度为 n 的字符串，要求字符串中最多包含一个 'A'，并且不能连续出现三个及以上的 'L'，问满足条件的字符串有多少个。

很明显需要使用动态规划求解。定义状态 dp[i][hadAbsent][ithState] 表示长度为i，以ithState（0：L; 1:P; 2:A）结尾，hadAbsent（0 ~ i-1，包含1/不包含0）'A'的字符串的个数。

状态转移方程为

  • dp[i][0][0] = dp[i-2][0][0] + 2*dp[i-2][0][1] LPL PPL PLL
  • dp[i][0][1] = dp[i-1][0][0] + dp[i-1][0][1] LP PP
  • dp[i][0][2] = dp[i-1][0][0] + dp[i-1][0][1] LA PA
  • dp[i][1][0] = dp[i-2][1][0] + 2*dp[i-2][1][1] + 2*dp[i-2][0][2] + dp[i-1][0][2] (A)LPL (A)PPL (A)PLL ALL APL AL
  • dp[i][1][1] = dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][0][2] (A)LP (A)PP AP

初始条件需要提前计算：

  • dp[0][0][0] = 1; L
  • dp[0][0][1] = 1; P
  • dp[0][0][2] = 1; A
  • dp[1][0][0] = 2; LL PL
  • dp[1][0][1] = 2; LP PP
  • dp[1][0][2] = 2; LA PA
  • dp[1][1][0] = 1; AL
  • dp[1][1][1] = 1; AP

模运算（取余）满足以下规律：

  • (a + b + c) % mod = ((a % mod) + (b % mod) + (c % mod)) % mod
  • (a * b * c) % mod = ((a % mod) * (b % mod) * (c % mod)) % mod

代码

/**
 * @date 2024-08-19 9:53
 */
public class CheckRecord552 {
    private static final int MOD = 1000000007;

    public int checkRecord(int n) {
        if (n == 1) {
            return 3;
        }
        long[][][] dp = new long[n][2][3];
        dp[0][0][0] = 1;
        dp[0][0][1] = 1;
        dp[0][0][2] = 1;

        dp[1][0][0] = 2;
        dp[1][0][1] = 2;
        dp[1][0][2] = 2;
        dp[1][1][0] = 1;
        dp[1][1][1] = 1;

        for (int i = 2; i < n; i++) {
            int pre = i - 1;
            int prepre = i - 2;
            dp[i][0][0] = (dp[prepre][0][0] + 2 * dp[prepre][0][1]) % MOD;
            dp[i][0][1] = (dp[pre][0][0] + dp[pre][0][1]) % MOD;
            dp[i][0][2] = (dp[pre][0][0] + dp[pre][0][1]) % MOD;
            dp[i][1][0] = (dp[prepre][1][0] + 2 * dp[prepre][1][1] + 2 * dp[prepre][0][2] + dp[pre][0][2]) % MOD;
            dp[i][1][1] = (dp[pre][1][0] + dp[pre][1][1] + dp[pre][0][2]) % MOD;
        }
        return (int) ((dp[n - 1][0][0] + dp[n - 1][0][1] + dp[n - 1][0][2] + dp[n - 1][1][0] + dp[n - 1][1][1]) % MOD);
    }

}

性能