552 Student Attendance Record II

552. Student Attendance Record II

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

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)