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 109 + 7.
A student attendance record is a string that only contains the following three characters:
'A' : Absent.
'L' : Late.
'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.

https://leetcode.com/problems/student-attendance-record-ii/discuss/101643

Solution：DP

思路：
DP
定义了三个DP数组P(Present), L(Late), A(Absent).
其中P[i]表示数组[0,i]范围内以P结尾的所有排列方式，L[i]表示数组[0,i]范围内以L结尾的所有排列方式，A[i]表示数组[0,i]范围内以A结尾的所有排列方式。
那么最终我们所求的就是P[n-1] + L[n-1] + A[n-1]了。

P, L, A数组的递推公式:

(1)P数组: P字符没有任何限制条件，可以跟在任何一个字符后面，所以有 P[i] = A[i-1] + P[i-1] + L[i-1]

(2)L数组的: L字符唯一的限制条件是不能有超过两个连续的L，那么在P和L字符后面可以加1一个L，如果前一个字符是L，我们要看再前面的一位是什么字符，如果是P或着A的话，可以加L，如果是L的话，就不能再加了，否则就连续3个了，所以有 L[i] = A[i-1] + P[i-1] + A[i-2] + P[i-2]

(3)A数组:这个比较麻烦，字符A的限制条件是整个字符串最多只能有1个A，那么当前一个字符是A的话，就不能再加A来，当前一个字符是P或者L的话，要确定之前从没有A出现过，才能加上A。那么实际上我们还需要定义两个数组P1, L1, 其中P1[i]表示数组[0,i]范围内以P结尾的不包含A的所有排列方式，L1[i]表示数组[0,i]范围内以L结尾的不包含A的所有排列方式，根据前两种情况我们不难推出P1和L1的递推公式，再加上A的递推公式如下：

A[i] = P1[i-1] + L1[i-1]

P1[i] = P1[i-1] + L1[i-1]
L1[i] = P1[i-1] + P1[i-2]
/*
将第二第三个等式多次带入第一个等式，就可以将P1和L1消掉，可以化简为：

A[i] = A[i-1] + A[i-2] + A[i-3]

这样就可以少定义两个数组P1, L1了，递推公式有了，代码也就不难写了.
*/

Time Complexity: O(N) Space Complexity: O(N)

Solution Code：

class Solution {
    public int checkRecord(int n) {
        if (n == 1) {
            return 3;
        }
        long[] dpL = new long[n]; // 只包含L和P，以 L 结尾的记录的数量
        long[] dpP = new long[n]; // 只包含L和P，以 P 结尾的记录的数量
        dpL[0] = 1;
        dpP[0] = 1;
        dpL[1] = 2;
        dpP[1] = 2;
        
        long[] A = new long[n];
        long[] L = new long[n];
        long[] P = new long[n];
        A[0] = 1;
        L[0] = 1;
        P[0] = 1;
        A[1] = 2;
        L[1] = 3;
        P[1] = 3;
        
        for (int i = 2; i < n; i++) {
            dpP[i] = (dpP[i - 1] + dpL[i - 1]) % 1000000007;
            dpL[i] = (dpP[i - 1] + dpP[i - 2]) % 1000000007;
            A[i] = dpP[i];
            L[i] = (A[i - 1] + A[i - 2] + P[i - 1] + P[i - 2]) % 1000000007;
            P[i] = (A[i - 1] + L[i - 1] + P[i - 1]) % 1000000007;
        }
        return (int)((A[n - 1] + L[n - 1] + P[n - 1]) % 1000000007);
    }
}