552. 学生出勤记录 II
可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
‘A’：Absent，缺勤
‘L’：Late，迟到
‘P’：Present，到场
如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
按 总出勤 计，学生缺勤（’A’）严格 少于两天。
学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（’L’）记录。
给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 109 + 7 取余 的结果。
示例 1：
输入：n = 2
输出：8
解释：
有 8 种长度为 2 的记录将被视为可奖励：
“PP” , “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”
只有”AA”不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。
题解：
因此在枚举/统计合法方案的个数时，当我们决策到某一位应该选什么时，我们关心的是当前方案中已经出现了多少个 A（以决策当前能否填入 A）以及连续出现的 L 的次数是多少（以决策当前能否填入 L）
法一：
记忆化搜索：同时由于我们在计算某个 (u, acnt, lcnt) 的方案数时，其依赖的状态可能会被重复使用，考虑加入记忆化，将结果缓存起来。
根据题意，n 的取值范围为 [0, n]，acntacnt 取值范围为 [0,1]，lcntlcnt 取值范围为 [0, 2]。
法二： 动态规划，既然可以用记忆化搜索，就可以动态规划
代码：
// 记忆化搜索 class Solution { public: int N; int dp[100003][3][3]; // dp[i][j][k]:表示i天，总共用j天缺勤，连续k天迟到 int mod=1e9+7; int dfs(int k,int a,int l) { if (a>1 || l>2) return 0; if(k>=N) return 1; if (dp[k][a][l]!=-1) return dp[k][a][l]; long long ans=0; ans=(ans+dfs(k+1,a+1,0))%mod; // 如果第k+1天，A ans=(ans+dfs(k+1,a,l+1))%mod; // L ans=(ans+dfs(k+1,a,0))%mod; // P return dp[k][a][l]=ans; } int checkRecord(int n) { N=n; memset(dp,-1,sizeof(dp)); dfs(0,0,0); return dp[0][0][0]; //为什么传回的是dp[0][0][0]需要理解 } };
动态规划：
//寻找状态转移过来的 class Solution { public: int checkRecord(int n) { int mod=1e9+7; int dp[100005][3][3]; memset(dp,0,sizeof(dp)); dp[0][0][0]=1; for(int i=1;i<=n;i++) { // 第i天，状态 P for(int j=0;j<=1;j++) for(int k=0;k<=2;k++) dp[i][j][0]=(dp[i][j][0]+dp[i-1][j][k])%mod; // 第i天， 状态 A for(int k=0;k<=2;k++) dp[i][1][0]=(dp[i][1][0]+dp[i-1][0][k])%mod; // 第i天， 状态为 L for(int j=0;j<=1;j++) for(int k=0;k<2;k++) dp[i][j][k+1]=(dp[i][j][k+1]+dp[i-1][j][k])%mod; } long long ans=0;; for(int j=0;j<=1;j++) for(int k=0;k<=2;k++) ans=(ans+dp[n][j][k])%mod; return (int)ans; } };