# 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 10^9 + 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.

```cpp
// Dynamic Programming
// P[i]: # of all rewardable records ending with P with length (i + 1)
// L[i]: # of all rewardable records ending with L with length (i + 1)
// A[i]: # of all rewardable records ending with A with length (i + 1)
// Target = P[n - 1] + L[n - 1] + A[n - 1] 
// Initial recursive relation:
// P[i] = A[i - 1] + L[i - 1] + P[i - 1], i >= 1
// L[i] = A[i - 1] + P[i - 1] + A[i - 2] + P[i - 2], i >= 2
// A[i] = noA_P[i - 1] + noA_L[i - 1], i >= 1
// noA_P[i] = noA_P[i - 1] + noA_L[i - 1], i >= 1
// noA_L[i] = noA_P[i - 1] + noA_P[i - 2], i >= 2
// Final recursive relation:
// P[i] = A[i - 1] + L[i - 1] + P[i - 1], i >= 1, P[0] = 1
// L[i] = A[i - 1] + P[i - 1] + A[i - 2] + P[i - 2], i >= 2 , L[0] = 1, L[1] = 3
// A[i] = A[i - 1] + A[i - 2] + A[i - 3], i >= 3, A[0] = 1, A[1] = 2, A[2] = 4
int checkRecord(int n) { // time: O(n); space: O(n)
    const int m = 1e9 + 7;
    vector<int> P(n), L(n), A(n);
    P[0] = L[0] = 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] = ( (A[i - 1] + L[i - 1]) % m + P[i - 1]) % m;
        if (i >= 2) L[i] = ( (A[i - 1] + P[i - 1]) % m + (A[i - 2] + P[i - 2]) % m) % m;
        if (i >= 3) A[i] = ( (A[i - 1] + A[i - 2]) % m + A[i - 3]) % m;
    }
    return ( (P.back() + L.back() ) % m + A.back() ) % m;
}
```
