[Hdp] lc552. 学生出勤记录 II(dp+递推+状态定义+状态转移+向前转移+好题)
文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接：552. 学生出勤记录 II
2. 题目解析
一道正常的线性dp 问题吧，状态定义和转移都不太难。分类讨论三种情况就行了。看到 y 总写了一个根据当前状态向前进行状态转移的方法，感觉还是值得记录一下的。避免某些情况下比较难写。可以对比下常规的状态转移方式和本次的状态转移方式，体会一下区别。
思路：
- 状态定义：f[i][j][k] 定义为长度为 i 的情况下，总共有 j 个 A，且末尾有连续个 L 的有效出勤方案数构成。
- 状态转移：f[i][j][k] 向前转移的方式，看看末尾添加这三种方式时，下一个状态可以变化到什么，然后再将状态转移过去即可。
- 填A：当 j 没有填过时，可以进行状态转移。状态将变为 f[i+1][j+1][0]。因为此时末尾已经变为 A，而非 L。
- 填L：当 k 没有连续填过两次时，可以进行状态转移。状态将变为 f[i+1][j][k+1]。因为此时末尾已经变为L，它不影响 A 的数量。
- 填P：这个没有什么限制，状态直接转移即可。状态将变为 f[i+1][j][0]
这个状态转移就是从当前位置推下一个位置是哪些，而非寻常的从当前位置，看看前一个位置是哪些。比较巧妙。
包括这个代码实现也是，细节点在于 i<n 的，因为在 i=n-1 时，会递推出来 i+1=n 的这一项状态值，所以也能算出结果。
另外也贴一下普通的状态转移代码，体会一下两者不同之处。
- 常规的转移方式，需要枚举每一个位置的前一位可以填什么，实际上大差不差。
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( 1 ) O(1) O(1)
class Solution {
public:int checkRecord(int n) {const int MOD = 1e9+7, N = 1e5+5;int f[N][2][3];memset(f, 0, sizeof(f));f[0][0][0] = 1;for (int i = 0; i < n; i ++ ) for (int j = 0; j < 2; j ++ )for (int k = 0; k < 3; k ++ ) {if (j < 1) f[i + 1][j + 1][0] = (f[i + 1][j + 1][0] + f[i][j][k]) % MOD; // 填A, 总数中不能出现两次 Aif (k + 1 <= 2) f[i + 1][j][k + 1] = (f[i + 1][j][k + 1] + f[i][j][k]) % MOD; // 填L, 连续的不能出现三次 Lf[i + 1][j][0] = (f[i + 1][j][0] + f[i][j][k]) % MOD; // 填P，这个肯定能转移，最后一位连续L 置为0 即可}int res = 0;for (int j = 0; j < 2; j ++ )for (int k = 0; k < 3; k ++ )res = (res + f[n][j][k]) % MOD;return res;}
};
常规转移：
class Solution {
public:int checkRecord(int n) {const int MOD = 1e9+7, N = 1e5+5;int f[N][2][3];memset(f, 0, sizeof(f));f[0][0][0] = 1;for (int i = 1; i <= n; i ++ ) {// 末尾填 pfor (int j = 0; j < 2; j ++ ) {for (int k = 0; k < 3; k ++ ) {f[i][j][0] = (f[i][j][0] + f[i - 1][j][k]) % MOD;}}// 末尾填 Afor (int k = 0; k < 3; k ++ ) {f[i][1][0] = (f[i][1][0] + f[i - 1][0][k]) % MOD;}// 末尾填 Lfor (int j = 0; j < 2; j ++ ) {for (int k = 1; k < 3; k ++ ) {f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - 1]) % MOD;}}} int res = 0;for (int j = 0; j < 2; j ++ )for (int k = 0; k < 3; k ++ )res = (res + f[n][j][k]) % MOD;return res;}
};