Dynamic Programming
An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:
- ‘A’: Absent.
- ‘L’: Late.
- ‘P’: Present.
Any student is eligible for an attendance award if they meet both of the following criteria:
- The student was absent (‘A’) for strictly fewer than 2 days total.
- The student was never late (‘L’) for 3 or more consecutive days.
Given an integer
n
, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 10**9 + 7.Constraints:
1 <= n <= 10**5
Example 1
Input: n = 2
Output: 8
Explanation: There are 8 records with length 2 that are eligible for an award:
"PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" is not eligible because there are 2 absences (there need to be fewer than 2).
Example 2
Input: n = 1
Output: 3
Example 3
Input: n = 10101
Output: 183236316
As this problem categorized in Hard, it is truly a hard problem. Easy solutions such as BSF or recursion get the Time Limit Exceeded error. So, it’s critical to improve the algorithm.
If we look into the problem well, we won’t take long to figure out this is a dynamic programming (DP) problem. A result of the given n depends on the result of n - 1 while n - 1 depends on n - 2. If we look into the problem further, we will realise the character pattern is not important. Looking at the number of patterns is the key to solve this problem. Again, if we look into the problem more, we will know it is a variation of famous Fibonacci sequence.
How to count is not straightforward like Fibonacci. The pattern counting is divided into two: with one A and without A. The initial values are based on n = 1.
The next state, n = 2, can be calculated as:
In the end, sum of all 6 patterns is the answer.
class StudentAttendanceRecordTwo {
public:
int checkRecord(int n) {
int mod = pow(10, 9) + 7;
long long int AnoL = 1, A1L = 0, A2L = 0, noAnoL = 1, noA1L = 1, noA2L = 0, tmp;
for (int i = 1; i < n; ++i) {
tmp = (AnoL + A1L + A2L + noAnoL + noA1L + noA2L) % mod;
A2L = A1L;
A1L = AnoL;
AnoL = tmp;
tmp = (noAnoL + noA1L + noA2L) % mod;
noA2L = noA1L;
noA1L = noAnoL;
noAnoL = tmp;
}
return (AnoL + A1L + A2L + noAnoL + noA1L + noA2L) % mod;
}
};
class StudentAttendanceRecordTwo:
def checkRecord(self, n: int) -> int:
mod = 10 ** 9 + 7
AnoL, A1L, A2L, noAnoL, noA1L, noA2L = 1, 0, 0, 1, 1, 0
for _ in range(1, n):
tmp = (AnoL + A1L + A2L + noAnoL + noA1L + noA2L) % mod
A1L, A2L = AnoL, A1L
AnoL = tmp
tmp = (noAnoL + noA1L + noA2L) % mod
noA1L, noA2L = noAnoL, noA1L
noAnoL = tmp
return (AnoL + A1L + A2L + noAnoL + noA1L + noA2L) % mod
MOD = 10 ** 9 + 7
# @param {Integer} n
# @return {Integer}
def check_record(n)
a_no_l, a_1_l, a_2_l, no_a_no_l, no_a_1_l, no_a_2_l = 1, 0, 0, 1, 1, 0
(1...n).each do |i|
tmp = [a_no_l, a_1_l, a_2_l, no_a_no_l, no_a_1_l, no_a_2_l].sum % MOD
a_1_l, a_2_l = a_no_l, a_1_l
a_no_l = tmp
tmp = [no_a_no_l, no_a_1_l, no_a_2_l].sum % MOD
no_a_1_l, no_a_2_l = no_a_no_l, no_a_1_l
no_a_no_l = tmp
end
[a_no_l, a_1_l, a_2_l, no_a_no_l, no_a_1_l, no_a_2_l].sum % MOD
end
O(n)
O(1)