552. Student Attendance Record II

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

Intuitive:

We found the smaller set of the problem also belongs to the same kind of problem.

-> It might be a DP problem.

So the next question is how to come out a suitable table for it.

And this part is usually the most difficult part. (How to narrow it ?) derive smaller table value to the next level table value.

DP[i] -> The combination count of the eligible attendance record, which size is i,

DP[i] = (The attendance record with size i-1, and End With P) + (The attendance record with size i-2, and End With P) + (The attendance record with size i, and End With P)

So, we define another table EndWithP[],

EndWithP[i] -> The combination count of the eligible attendance record, which size is i, and end With P

-> DP[i] = EndWithP[i] + EndWithP[i-1] + EndWithP[i-2];

-> EndWithP[i] = DP[i-1]

And the DP[n] will be the combination count that without any Absent in the record

The Next step is to add on the combination count with an absent in the record.

An absent record can split the record into 2 parts, [0...i-1] A [i+1....n-1]

So the index will be the first part's length, and n - i - 1 will be the second parts length

For each possible index of absent record, we need to add on the combination count of each sides.

dp[i] * dp[n-i-1], for all i in [0....n]

class Solution {
    long mod = 1000000007;
    public int checkRecord(int n) {
        long[] endP = new long[n+1];
        long[] endPorL = new long[n+1];
        endP[0] = endPorL[0] = 1;
        endP[1] = 1;
        endPorL[1] = 2;
        for(int i = 2; i <= n; i++) {
            endP[i] = endPorL[i-1];
            endPorL[i] = ( endP[i] + endP[i-1] + endP[i-2])% mod;
        }
        long ans = endPorL[n]; //w/o absent
        for(int i = 0; i < n; i++) {
            long count = (endPorL[i] * endPorL[n-i-1]) % mod;
            ans = (ans + count) % mod; // with absent
        }
        return (int)ans;
    }
}