C ++中的学生出勤记录II

假设我们有一个正整数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