学生出勤记录 II

Category Difficulty Likes Dislikes
algorithms Hard (57.61%) 279 -
Tags

dynamic-programming

Companies

google

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

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

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

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

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

示例 1：

1
2
3
4
5
6
输入：n = 2
输出：8
解释：
有 8 种长度为 2 的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL" 
只有"AA"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。

示例 2：

1
2
输入：n = 1
输出：3

示例 3：

1
2
输入：n = 10101
输出：183236316

提示：

  • 1 <= n <= 105

模拟(c++)

1
2
3
4
5
6
7
A L P
AL AP LL LA LP PL PP PA
ALL ALP APL APP LLA LLP LAL LAP LPA LPL LPP PLA PLL PLP PPA PPL PPP PAL PAP

f = [i][j][2] 
i = 1 ~ n - 1, j = 0 ~ f[i - 1].size() - 1
f[i][j] = C(f[i - 1][j][1]) + f[i - 1][j][0] == 0 ?  push(1, 0)

C(f[i - 1][j][1])表示的是结尾L的个数，f[i - 1][j][0] == 0判断这个字符串中有无A，如果没有就在结尾添加一个A，f[i - 1][j][1]则为0

1
2
3
4
if ch == '1*L' LL LP
else if ch == '2*L' LP
else if ch == '0*L' PP PL
if ch == '0*A' PA LA

P结尾 = 0*L结尾

因为n值越大，f[i-1].size()越大，效率太低，不通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem552.h"

using namespace std;
// @before-stub-for-debug-end

/*

 * @lc app=leetcode.cn id=552 lang=cpp
   *
 * [552] 学生出勤记录 II
   */

/** 

 * A L P
 * AL AP LL LA LP PL PP PA
 * ALL ALP APL APP LLA LLP LAL LAP LPA LPL LPP PLA PLL PLP PPA PPL PPP PAL PAP
 * 
 * ch = 'L' && 'L' < 3
 * i < n > 0, j < f(i - 1).size()
 * 
 * if ch == '1*L' LL LP
 * else if ch == '2*L' LP
 * else if ch == '0*L' PP PL
 * if ch == '0*A' PA LA
 * */

// @lc code=start
class Solution {
public:
    int checkRecord(int n) {
        vector<vector<vector<int>>> f(0, vector<vector<int>>(0, vector<int>(2, 0)));
        f.push_back({{{1}, {0}}, {{0}, {1}}, {{0}, {0}}});
        for (int i = 1; i < n; ++i) {
            vector<vector<int>> tmp;
            for (int j = 0; j < f[i - 1].size(); ++j) {
                int l = f[i - 1][j][1], a = f[i - 1][j][0];
                if (l == 1) {
                    tmp.push_back({{a}, {2}});
                    tmp.push_back({{a}, {0}});
                } else if (l == 2) {
                    tmp.push_back({{a}, {0}});
                } else if (l == 0) {
                    tmp.push_back({{a}, {0}});
                    tmp.push_back({{a}, {1}});
                }
                if (a == 0) {
                    tmp.push_back({{1}, {0}});
                }
            }
            f.push_back(tmp);
        }
        return f[f.size()-1].size();
    }
};
// @lc code=end

动态规划(c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem552.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=552 lang=cpp
 *
 * [552] 学生出勤记录 II
 */

/** 
 * A L P
 * AL AP LL LA LP PL PP PA
 * ALL ALP APL APP LLA LLP LAL LAP LPA LPL LPP PLA PLL PLP PPA PPL PPP PAL PAP
 * 
 * f[i][j][0] 
 * 
 * ch = 'L' && 'L' < 3
 * i < n > 0, j < f(i - 1).size()
 * 
 * if ch == '1*L' LL LP
 * else if ch == '2*L' LP
 * else if ch == '0*L' PP PL
 * if ch == '0*A' PA LA
 * 
 */


// @lc code=start
class Solution {
public:
    static constexpr int MOD = 1'000'000'007;
    int checkRecord(int n) {
        /** 
         * 超时
         */
        // vector<vector<vector<int>>> f(0, vector<vector<int>>(0, vector<int>(2, 0)));
        // f.push_back({{{1}, {0}}, {{0}, {1}}, {{0}, {0}}});
        // for (int i = 1; i < n; ++i) {
        //     vector<vector<int>> tmp;
        //     for (int j = 0; j < f[i - 1].size(); ++j) {
        //         int l = f[i - 1][j][1], a = f[i - 1][j][0];
        //         if (l == 1) {
        //             tmp.push_back({{a}, {2}});
        //             tmp.push_back({{a}, {0}});
        //         } else if (l == 2) {
        //             tmp.push_back({{a}, {0}});
        //         } else if (l == 0) {
        //             tmp.push_back({{a}, {0}});
        //             tmp.push_back({{a}, {1}});
        //         }
        //         if (a == 0) {
        //             tmp.push_back({{1}, {0}});
        //         }
        //     }
        //     f.push_back(tmp);
        // }
        // return f[f.size()-1].size();
        vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(2, vector<int>(3, 0)));
        f[0][0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 3; ++k) {
                    f[i][j][0] = (f[i][j][0] + f[i - 1][j][k]) % MOD;
                }
            }
            for (int k = 0; k < 3; ++k) {
                f[i][1][0] = (f[i][1][0] + f[i - 1][0][k]) % MOD;
            }
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    f[i][j][k + 1] = (f[i][j][k + 1] + f[i - 1][j][k]) % MOD;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                res = (res + f[n][i][j]) % MOD;
            }
        }
        return res;
    }
};
// @lc code=end