题目：
可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
'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
提示：
1 <= n <= 105
暴力回溯
思路：
答案是要返回有多少种满足获取奖励的情况，那么其实就是从所有情况里面挑
很明显，这里用回溯算法就可以获取所有情况 （3^n种)，那么接下去要考虑的就是怎么样判断符合条件的情况，然后进行剪枝
满足条件有两个：
第一：A出现的次数不超过2
第二：没有连续出现3个L
那么我们回溯时就携带两个参数 cntA：当前枚举出现A的次数， cntL：当前枚举末尾出现L的次数
只要枚举字母的总数达到 n 就是一个答案，每次枚举都是三选一
回溯终止条件是：cntA >= 2 || cntL >= 3
代码：
class Solution
{
public:
vector<char> path;
int ans = 0;
int mod = 1e9 + 7;
// cntA:path中A出现的次数, cntL: path末尾出现的L次数
void backTrack(int n, int cntA, int cntL)
{
if (cntA == 2) return;
if (cntL == 3) return;
if (path.size() == n) {
ans = (ans + 1) % mod;
//for (int i = 0; i < n; i++) cout << path[i] << " ";
//cout << endl;
return;
}
// 放置 A
path.push_back('A');
backTrack(n, cntA + 1, 0);
path.pop_back();
// 放置 L
path.push_back('L');
backTrack(n, cntA, cntL + 1);
path.pop_back();
// 放置 P
path.push_back('P');
backTrack(n, cntA, 0);
path.pop_back();
}
int checkRecord(int n)
{
backTrack(n, 0, 0);
return ans;
}
};
记忆化搜索
思路：
一、寻找子问题
本题要构造长为 n 的字符串 s，同时满足：
s 至多包含 1 个 A。
s 不包含 LLL，也就是说，至多有 2 个连续的 L。
从右往左填入字母。一开始，右边填的字母不含 A，且上一个填的字母不是 L。
考虑 s 的最后一个位置填什么字母：
填 P，接下来要解决的问题是：在右边填的字母不含 A，且上一个填的字母不是 L 的情况下，继续向左填字母，能构造多少个长为 n − 1 的字符串。
填 A，接下来要解决的问题是：在右边填的字母包含 A，且上一个填的字母不是 L 的情况下，继续向左填字母，能构造多少个长为 n − 1 的字符串。在这种情况下，后续位置不能填 A。
填 L，接下来要解决的问题是：在右边填的字母不含 A，且上一个填的字母是 L 的情况下，继续向左填字母，能构造多少个长为 n − 1 的字符串。如果继续填 L，问题变成，在右边填的字母不含 A，且右边相邻位置有 2 个连续 L 的情况下，继续向左填字母，能构造多少个长为 n − 2 的字符串。在这种情况下，下一个位置不能填 L。
这些问题都是和原问题相似的、规模更小的子问题，可以用递归解决。
注：从右往左思考，主要是为了方便把递归翻译成递推。从左往右思考也是可以的。
二、状态定义与状态转移方程
因为要解决的问题都形如「在右边填了 j 个 A，且右边相邻位置有 k 个连续 L 的情况下，继续向左填字母，能构造多少个长为 i 的字符串」，所以用它作为本题的状态定义 dfs(i, j, k)。
考虑长为 i 的字符串的最后一个位置填什么字母：
填 P，接下来要解决的问题是：在右边填了 j 个 A，且右边相邻位置有 0 个连续 L 的情况下，继续向左填字母，能构造多少个长为 i − 1 的字符串，即 dfs(i − 1, j, 0)。
如果 j = 0，那么可以填 A，接下来要解决的问题是：在右边填了 1 个 A，且右边相邻位置有 0 个连续 L 的情况下，继续向左填字母，能构造多少个长为 i−1 的字符串，即 dfs(i − 1, 1, 0)。
如果 k < 2，那么可以填 L，接下来要解决的问题是：在右边填了 j 个 A，且右边相邻位置有 k + 1 个连续 L 的情况下，继续向左填字母，能构造多少个长为 i−1 的字符串，即 dfs(i − 1, j, k + 1)。
由于最后一个位置填的字母不同，所以三种情况互相独立，根据加法原理，将上述方案数相加，即为 dfs(i, j, k)。
递归边界：dfs(0, j, k) = 1。如果能递归到 i = 0 的状态，说明我们找到了一个合法方案，返回 1。
递归入口：dfs(n,0,0)，也就是答案。
三、递归搜索 + 保存递归返回值 = 记忆化搜索
考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：
如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 memo 数组中。
如果一个状态不是第一次遇到（memo 中保存的结果不等于 memo 的初始值），那么可以直接返回 memo 中保存的结果。
注意：memo 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 0，并且要记忆化的 dfs(i, j, k) 也等于 0，那就没法判断 0 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 −1。
本题方案数均为正数，初始化成 0 也可以。
代码：
/*
咋一看好像和暴力回溯差不多，但是时间复杂度大幅降低
这是为什么呢？
关键就在于遍历顺序，暴力回溯是从前往后遍历，记忆化搜索是从后往前遍历
在记忆化搜索的实现中，由于记忆好了后面 k 个固定字母，那么就不用重新搜索了
*/
class Solution {
public:
const int MOD = 1e9 + 7;
const static int MX = 1e5 + 1;
int memo[MX][2][3];
int dfs(int i, int j, int k) {
if (i == 0) return 1;
int& res = memo[i][j][k]; // 这里写引用，那么更新res时会自动更新 memo[i][j][j];
if (res) return res;
res = dfs(i - 1, j, 0); // 放置P
if (j == 0) res = (res + dfs(i - 1, 1, 0)) % MOD; // 放置 A
if (k < 2) res = (res + dfs(i - 1, j, k + 1)) % MOD; // 放置L
return res;
}
int checkRecord(int n) {
return dfs(n, 0, 0);
}
};