假设我们有一个正整数n，我们必须找到长度为n的所有可能的出勤记录数，这将被认为是有奖励的。由于答案可能非常大，我们将使用mod 109 + 7将其返回。
在学生出勤记录中，字符串只能包含以下三个字符-
“ A”表示不存在。
“ L”表示迟到。
“ P”表示存在。
如果一次出席的出席人数不超过一个“ A”（缺席）或不超过两个连续的“ L”（后期），则被视为奖励。因此，我们必须找到最高点。
如果输入为2，则输出为8，因为我们可以生成8种可能的奖励方式，即[PP，AP，PA，LP，PL，AL，LA，LL]，只有AA不会在那里。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数add()，这将需要a，b，
return（（a mod m）+（b mod m））mod m
在主要方法中，请执行以下操作：
定义大小为n + 1的数组p，大小为n + 1的数组a，大小为n + 1的数组l，大小为n + 1的数组ap和大小为n + 1的数组a1
如果n与1相同，则-
返回3
p [0]：= 1，p [1]：= 1，p [2]：= 3
a [0]：= 1，a [1]：= 1，a [2]：= 2
l [0]：= 1，l [1]：= 1，l [2]：= 3
ap [0]：= 1，ap [1]：= 1，ap [2]：= 2
al [0]：= 1，al [1]：= 1，al [2]：= 2
对于初始化i：= 3，当i <= n时，更新（将i增加1），执行-
p [i]：= add（add（p [i-1]，a [i-1]），l [i-1]）
l [i]：=添加（add（p [i-1]，p [i-2]），add（a [i-1]，a [i-2]））
a [i]：= add（al [i-1]，ap [i-1]）
al [i]：= add（ap [i-1]，ap [i-2]）
ap [i]：= add（ap [i-1]，al [i-1]）
返回add（add（p [n]，l [n]），a [n]）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ( (a % m) + (b % m) ) % m;
}
int checkRecord(int n) {
vector <int> p(n+1), a(n+1), l(n+1), ap(n+1), al(n+1);
if(n == 1)return 3;
p[0] = 1;
p[1] = 1;
p[2] = 3;
a[0] = 1;
a[1] = 1;
a[2] = 2;
l[0] = 1;
l[1] = 1;
l[2] = 3;
ap[0] = 1;
ap[1] = 1;
ap[2] = 2;
al[0] = 1;
al[1] = 1;
al[2] = 2;
for(int i = 3; i <= n; i++){
p[i] = add(add(p[i-1], a[i-1]), l[i-1]);
l[i] = add(add(p[i-1], p[i-2]),add(a[i-1] , a[i-2]));
a[i] = add(al[i-1], ap[i-1]);
al[i] = add(ap[i-1], ap[i-2]);
ap[i] = add(ap[i-1], al[i-1]);
}
return add(add(p[n], l[n]), a[n]);
}
};
main(){
Solution ob;
cout << (ob.checkRecord(3));
}3
输出结果
19