C ++中的学生出勤记录II
假设我们有一个正整数n，我们必须找到长度为n的所有可能的出勤记录数，这将被认为是有奖励的。由于答案可能非常大，我们将使用mod109+7将其返回。
在学生出勤记录中，字符串只能包含以下三个字符-
“A”表示不存在。
“L”表示迟到。
“P”表示存在。
如果一次出席的出席人数不超过一个“A”（缺席）或不超过两个连续的“L”（后期），则被视为奖励。因此，我们必须找到最高点。
如果输入为2，则输出为8，因为我们可以生成8种可能的奖励方式，即[PP，AP，PA，LP，PL，AL，LA，LL]，只有AA不会在那里。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数add()，这将需要a，b，
return（（amodm）+（bmodm））modm
在主要方法中，请执行以下操作：
定义大小为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