Leetcode-552 学生出勤记录II
Leetcode-552 学生出勤记录II
- 1. 题目描述
- 2. 解题思路
- 3. 代码实现
1. 题目描述
Leetcode-552 学生出勤记录II
2. 解题思路
(1) 使用记忆化搜索来实现；
(2) 定义f[i][j][k]为右边填写j个A, 且右边相邻位置有k个连续的L的情况下，向左填字母能构造多少个长为i的字符串；
(3) 对于每次填字符有三种可能分别列出其递推表达式，求出最终的结果。
3. 代码实现
const int MOD = 1'000'000'007;class Solution {
public:int checkRecord(int n) {// 定义f[i][j][k]为右边填写j个A, 且右边相邻位置有k个连续的L的情况下// 向左填字母能构造多少个长为i的字符串// 初始化操作int f[n + 1][2][3];for (int i = 0; i <= 1; i++) {for (int j = 0; j <= 2; j++) {f[0][i][j] = 1;}}for (int i = 1; i <= n; i++) {for (int j = 0; j < 2; j++) {for (int k = 0; k < 3; k++) {int res = f[i - 1][j][0]; // 填pif (j == 0) {res = (res + f[i - 1][1][0]) % MOD; // 填A}if (k < 2) {res = (res + f[i - 1][j][k + 1]) % MOD; // 填L}f[i][j][k] = res;}}}return f[n][0][0];}
};