552. Student Attendance Record II

Problem Link

Description

---

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 109 + 7.

 

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

 

Constraints:

• 1 <= n <= 105

Solution

---

Python3

MOD = 10 ** 9 + 7
 
@cache
def dp(index, absent, late):
    if index == 0: return 1
 
    res = dp(index - 1, absent, 0) # present
    res %= MOD
    if absent + 1 < 2:
        res += dp(index - 1, absent + 1, 0) # absent
        res %= MOD
    if late + 1 < 3:
        res += dp(index - 1, absent, late + 1) # late
        res %= MOD
    
    return res
 
class Solution:
    def checkRecord(self, n: int) -> int:
        return dp(n, 0, 0)

C++

class Solution {
public:
    int dp[100005][2][3];
    int MOD = 1e9 + 7;
 
    long long solve(int index, int absent, int late) {
        if (absent == 2 || late == 3) return 0LL;
        if (index == 0) return 1LL;
 
        if (dp[index][absent][late] != -1) return dp[index][absent][late];
 
        long long res = solve(index - 1, absent, 0) % MOD;
        res = (res + solve(index - 1, absent + 1, 0) % MOD) % MOD;
        res = (res + solve(index - 1, absent, late + 1) % MOD) % MOD;
 
        return dp[index][absent][late] = res;
    }
 
    int checkRecord(int n) {
        memset(dp, -1, sizeof (dp));
        return solve(n, 0, 0);
    }
};