题目：552. 学生出勤记录 II
思路：记忆化搜索dfs，细节看注释
class Solution {
public:
const int mod=1e9+7;
//状态f[u][a][b]表示：在选择第u个位置前，缺勤次数为a次，且当前连续迟到次数为b次时，可以得到的合法出勤次数
int f[100010][5][5];
int dfs(int u,int a,int b){
//出现不合法状态，直接返回0
if(a>1||b>2) return 0;
//当前位置已处理完，且都合法，返回1即可
if(u<0) return 1;
//记忆化，当前转态已出现过，直接返回答案
if(f[u][a][b]!=-1) return f[u][a][b];
int res=0;
//到场、缺勤、迟到
res=((long long)dfs(u-1,a,0)+dfs(u-1,a+1,0)+dfs(u-1,a,b+1))%mod;
return f[u][a][b]=res;
}
int checkRecord(int n) {
memset(f,-1,sizeof f);
return dfs(n-1,0,0);
}
};