Leetcode 552.学生出勤记录II

学生出勤记录II

给定一个正整数 n，返回长度为 n 的所有可被视为可奖励的出勤记录的数量。答案可能非常大，你只需返回结果mod 10⁹ + 7的值。

学生出勤记录是只包含以下三个字符的字符串：

'A' : Absent，缺勤
'L' : Late，迟到
'P' : Present，到场

如果记录不包含多于一个'A'（缺勤）或超过两个连续的'L'（迟到），则该记录被视为可奖励的。

示例 1:

输入: n = 2

输出: 8

解释：

有8个长度为2的记录将被视为可奖励：

"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"

只有"AA"不会被视为可奖励，因为缺勤次数超过一次。

注意：n 的值不会超过100000。

思路

首先，定义几个函数

Total(n): 字符长度为n的符合条件的个数

P(n): 字符长度为n的并且最后一位为P的符合条件的个数

L(n): 字符长度为n的并且最后一位为L的符合条件的个数

A(n):字符长度为n的并且最后一位为A的符合条件的个数

noAP(n):字符长度为n的并且没有一个A字符而且最后一位为P的符合条件的个数

noAL(n):字符长度为n的并且没有一个A字符而且最后一位为L的符合条件的个数

根据定义，可以得到

Total(n) = P(n) + L(n) + A(n); (n>=1)

P(n) = P(n-1) + L(n-1) + A(n-1); (n>=2)

然后由于规则规定不能有三个连续一起L字符，不然判定不符合条件，所以

L(n) = P(n-1) + A(n-1) + P(n-2) + A(n-2); (n>=3)

而且最多只能有一个A字符，因此

A(n) = noAP(n-1) + noAL(n-1); (n>=2)

同时，

noAP(n) = noAP(n-1) + noAL(n-1); (n>=2)

noAL(n) = noAP(n-1) + noAP(n-2); (n>=3)

由上面的关系式，然后我们再初始化一些条件，

P(1) = A(1) = L(1) = 1;

L(2) = 1;

noAL(1) = noAP(1) = 1;

noAL(2) = noAP(2) = 2;

 1 class Solution {
 2     public:
 3     int checkRecord(int n) {
 4         if (n == 1) return 3;
 5         int mod = 1000000007;
 6         int* A = new int[n + 1];
 7         int* L = new int[n + 1];
 8         int* P = new int[n + 1];
 9         int* noAL = new int[n + 1];
10         int* noAP = new int[n + 1];
11         //int A[10], L[10], P[10], noAL[10], noAP[10]; 
12         A[1] = L[1] = P[1] = 1;
13         L[2] = 3;
14         noAL[1] = noAP[1] = 1;
15         noAL[2] = noAP[2] = 2;
16         for (int i = 2; i <= n; i++) {
17             P[i] = ((P[i - 1] + A[i - 1])%mod + L[i - 1])%mod;
18             A[i] = (noAP[i - 1] + noAL[i - 1]) % mod;
19             noAP[i] = (noAP[i - 1] + noAL[i - 1]) % mod;
20             if (i >= 3) {
21                 L[i] = ((P[i - 1] + A[i - 1]) % mod + (A[i - 2] + P[i - 2]) % mod) % mod;
22                 noAL[i] = (noAP[i - 1] + noAP[i - 2]) % mod;
23             }
24         }
25         return ((A[n] + P[n]) % mod + L[n]) % mod;
26     }
27 };