552. 学生出勤记录 II (Hard)

问题描述

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

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

解题思路

dp思路1

考虑dp2[i][0]为只有迟到和到场两种情况下，第i + 1天迟到的情况数，dp2[i][1]为第i + 1天到场的情况数，则递推关系为:

dp2[i][1] = dp2[i - 1][0] + dp2[i - 1][1];
dp2[i][0] = dp2[i - 1][1] + dp2[i - 1][0] - dp2[n - 3][1];

考虑dp[i][0]为第i + 1天迟到的情况数，dp[i][1]为第i + 1天到场的情况数，dp[i][2]为第i + 1天缺席的情况数，则递推关系有：

dp[i][1] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
dp[i][2] = dp2[i - 1][0] + dp2[i - 1][1];
dp[i][0] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][0] - (dp[i - 3][1] + dp[i - 3][2]);

注意取模

dp思路2

代码

class Solution {

  public:

    int checkRecord(int n) {

        if (n == 1)

            return 3;

        if (n == 2)

            return 8;

        if (n == 3)

            return 19;

        vector<vector<long long>> dp3(n + 1, vector<long long>(3, 0));

        vector<vector<long long>> dp2(n, vector<long long>(2, 0));

        int mod = 1000000007;

        // 0表示迟到，1表示到场，2表示缺勤

        dp2[0][0] = dp2[0][1] = 1;

        dp2[1][0] = dp2[1][1] = 2;

        dp2[2][0] = 3;

        dp2[2][1] = 4;

        for (int i = 3; i < n; i++) {

            dp2[i][1] = (dp2[i - 1][0] % mod + dp2[i - 1][1] % mod) % mod;

            dp2[i][0] = (dp2[i - 1][1] % mod + (dp2[i - 1][0] - dp2[i - 3][1] + mod) % mod) % mod;

        }

        dp3[0][1] = dp3[0][0] = dp3[0][2] = 1;

        dp3[1][0] = 3, dp3[1][1] = 3, dp3[1][2] = 2;

        dp3[2][0] = 3 + 2 + 3 - 1, dp3[2][1] = 8, dp3[2][2] = 4;

        for (int i = 1; i < n; i++) {

            dp3[i][2] = (dp2[i - 1][0] % mod + dp2[i - 1][1] % mod) % mod;

        }

        for (int i = 3; i < n; i++) {

            dp3[i][0] = (dp3[i - 1][1] % mod + dp3[i - 1][2] % mod + (dp3[i - 1][0] - (dp3[i - 3][1] + dp3[i - 3][2]) + mod) % mod) % mod;

            dp3[i][1] = (dp3[i - 1][1] % mod + dp3[i - 1][0] % mod + dp3[i - 1][2] % mod) % mod;

        }

        return (dp3[n - 1][0] + dp3[n - 1][1] + dp3[n - 1][2]) % mod;

    }

};

巴特西

552. 学生出勤记录 II (Hard)

问题描述

解题思路

dp思路1

dp思路2

代码

最新文章

热门文章