来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/student-attendance-record-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 次）。
示例 2：
输入：n = 1
输出：3
示例 3：
输入：n = 10101
输出：183236316
题目分析：
- 总共的A不能超过2次：A出现0次和1次。
- 连续的L不能超过3次：连续L出现次数0次，1次，2次。
思路一：
直接深度遍历（超时）
class Solution {
public int mod = (int) 1e9+7;
public int count;
public int checkRecord(int n) {
count = n;
int result = dfs(0, 0, 0);
return result;
}
public int dfs(int num, int absent, int late) {
if (num == count) return 1;
int result = 0;
result += dfs(num + 1, absent, 0);
if (absent < 1) { // 缺勤最多1次
result += dfs(num + 1, 1, 0);
}
if (late < 2) { // 连续迟到最多2次
result += dfs(num + 1, absent, late + 1);
}
result = result % mod;
return result;
}
}
思路二：
观察暴力dfs可以发现，有很多场景进行了重复递归，可以使用记忆化搜索进行优化.
class Solution {
public int mod = (int) 1e9+7;
public int count;
public int[][][] arr;
public int checkRecord(int n) {
count = n;
arr = new int[n][2][3];
int result = dfs(0, 0, 0);
return result;
}
public int dfs(int num, int absent, int late) {
if (num == count) return 1;
if (arr[num][absent][late] != 0) return arr[num][absent][late]; // 对于相同num,absent,late的情况，减枝。
int result = 0;
result += dfs(num + 1, absent, 0);
result %= mod;
if (absent < 1) { // 缺勤最多1次
result += dfs(num + 1, 1, 0);
result %= mod;
}
if (late < 2) { // 连续迟到最多2次
result += dfs(num + 1, absent, late + 1);
result %= mod;
}
arr[num][absent][late] = result; // 记录num,absent,late情况时的数量，用于减枝。
return result;
}
}
