552. Student Attendance Record II

Given a positive integer n , return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 109 + 7.

A student attendance record is a string that only contains the following three characters:

1. ‘A’ : Absent.
2. ‘L’ : Late.
3. ‘P’ : Present.

A record is regarded as rewardable if it doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

Example 1:

**Input:** n = 2
**Output:** 8
**Explanation:**
There are 8 records with length 2 will be regarded as rewardable:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" won't be regarded as rewardable owing to more than one absent times.

Note: The value of n won’t exceed 100,000.

class Solution {
public:
int checkRecord(int n) {
int M = 1e9 + 7;
int dp[n + 1][2][3] = {0};
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 3; ++k) {
dp[0][j][k] = 1;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 3; ++k) {
int val = dp[i - 1][j][2];
if (j > 0) val = (val + dp[i - 1][j - 1][2]) % M;
if (k > 0) val = (val + dp[i - 1][j][k - 1]) % M;
dp[i][j][k] = val;
}
}
}
return dp[n][1][2];
}
};

A[i] = P1[i-1] + L1[i-1]

P1[i] = P1[i-1] + L1[i-1]

L1[i] = P1[i-1] + P1[i-2]

A[i] = A[i-1] + A[i-2] + A[i-3]

class Solution {
public:
int checkRecord(int n) {
int M = 1e9 + 7;
vector<int> P(n), L(n), A(n);
P[0] = 1; L[0] = 1; A[0] = 1;
if (n > 1) { L[1] = 3; A[1] = 2; }
if (n > 2) A[2] = 4;
for (int i = 1; i < n; ++i) {
P[i] = ((P[i - 1] + L[i - 1]) % M + A[i - 1]) % M;
if (i > 1) L[i] = ((A[i - 1] + P[i - 1]) % M + (A[i - 2] + P[i - 2]) % M) % M;
if (i > 2) A[i] = ((A[i - 1] + A[i - 2]) % M + A[i - 3]) % M;
}
return ((A[n - 1] + P[n - 1]) % M + L[n - 1]) % M;
}
};

class Solution {
public:
int checkRecord(int n) {
int M = 1e9 + 7;
vector<long> P(n + 1), PorL(n + 1);
P[0] = 1; PorL[0] = 1; PorL[1] = 2;
for (int i = 1; i <= n; ++i) {
P[i] = PorL[i - 1];
if (i > 1) PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M;
}
long res = PorL[n];
for (int i = 0; i < n; ++i) {
long t = (PorL[i] * PorL[n - 1 - i]) % M;
res = (res + t) % M;
}
return res;
}
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/552

Student Attendance Record I

https://leetcode.com/problems/student-attendance-record-ii/

https://leetcode.com/problems/student-attendance-record-ii/discuss/101638/Simple-Java-O(n)-solution

https://leetcode.com/problems/student-attendance-record-ii/discuss/101633/Improving-the-runtime-from-O(n)-to-O(log-n)

https://leetcode.com/problems/student-attendance-record-ii/discuss/101643/Share-my-O(n)-C%2B%2B-DP-solution-with-thinking-process-and-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation