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.

//Absent : 1, 0 only
//Late : not consequtive 3times (2, 1, 0 only)
//range : 0 ... 100000
class Solution {
    int dp[100001][2][3];
    int mod = 1e9 + 7;
    int solution(int day, int absent, int late) {
        if(dp[day][absent][late] != -1) return dp[day][absent][late];
        dp[day][absent][late] = solution(day + 1, absent, 0); //attendance;
        if(!absent) {
            dp[day][absent][late] = (dp[day][absent][late] + solution(day + 1, absent + 1, 0)) % mod; //if can absent, absent today;
        }
        if(late < 2) {
            dp[day][absent][late] = (dp[day][absent][late] + solution(day + 1, absent, late + 1)) % mod; //if can late, late today;
        }
        return dp[day][absent][late];
    }
public:
    int checkRecord(int n) {
        memset(dp,-1,sizeof(dp));
        dp[n][0][0] = dp[n][0][1] = dp[n][0][2] = dp[n][1][0] = dp[n][1][1] = dp[n][1][2] = 1;
        return solution(0,0,0);
    }
};