# 552     Student Attendance Record II

## 552. [Student Attendance Record II](https://leetcode.com/problems/student-attendance-record-ii/description/)

## 1. Question

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

## 2. Implementation

**(1) DP (数学推导)**

思路: 我们定义T(n)为长度为n的rewardable records, T(n) = P(n) + L(n) + A(n)

1. P(n)是长度为n的以P结尾的record， P(n) = P(n - 1) + A(n - 1) + L(n - 1), P(1), P(2) = 3
2. L(n)是长度为n的以L结尾的record,  L(n) = P(n - 1) + A(n - 1) + P(n - 2) + A(n - 2), L(1) = 1, L(2) = 3
3. A(n)是长度为n的以A结尾的record, noAP(n)是长度为n以P结尾且没有A的record, noAL(n)是长度为n以L结尾且没有A的record, A(n) = noAP(n - 1) + noAL(n - 1)
4. noAP(n) = noAP(n - 1) + noAL(n - 1), noAL(n) = noAP(n - 1) + noAP(n - 2), 通过观察可以得知noAP(n) = A(n), 将此代入noAL(n)的等式可以得出noAL(n) = A(n - 1) + A(n - 2)
5. 将noAP(n) = A(n)和noAL(n) = A(n - 1) + A(n - 2)代入A(n) = noAP(n - 1) + noAL(n - 1),得出A(n) = A(n - 1) + A(n - 2) + A(n - 3), A(1) = 1, A(2) = 2, A(3) = 4
6. 具体推导过程可参考<https://discuss.leetcode.com/topic/86696/share-my-o-n-c-dp-solution-with-thinking-process-and-explanation/2>

```java
class Solution {
    public int checkRecord(int n) {
        if (n == 1) {
            return 3;
        }

        int M = 1000000007;

        int[] p = new int[n];
        int[] l = new int[n];
        int[] a = new int[n];

        // 由于数组以0开始,p[0] 相当于长度为1的以P结尾的record
        p[0] = 1;
        p[1] = 3;
        l[0] = 1;
        l[1] = 3;
        a[0] = 1;
        a[1] = 2;

        if (n == 2) {
            return p[1] + a[1] + l[1];
        }

        //以a结尾，长度为3的record只有4种，因为a不能出现两次，所以前面两位都是p和l的排列组合 (2 * 2 = 4)
        a[2] = 4;

        for (int i = 2; i < n; i++) {
            p[i] = ((p[i - 1] + a[i - 1]) % M + l[i - 1]) % M;

            l[i] = ((p[i - 1] + p[i - 2]) % M + (a[i - 1] + a[i - 2]) % M) % M; 

            if (i >= 3) {
                a[i] = ((a[i - 1] + a[i - 2]) % M + a[i - 3]) % M;
            }
        }
        return ((p[n - 1] + a[n - 1]) % M + l[n - 1]) % M;
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(n)