题意ref{:target=”_blank”}
动态规划,三个维度,从 f[i][j][k] 开始向后转移,注意第三维置零的情况,即absent和present状态下的late不连续了
C++ 代码
class Solution {
public:
int checkRecord(int n) {
const int MOD = 1e9 + 7;
// f[i][j][k] 表示 前i个字符,absent的数量是j(0,1),连续late数量k(0,1,2)
// j的合法值是0,1; k的合法值是0,1,2
int f[n+1][2][3];
memset(f, 0, sizeof(f));
f[0][0][0] = 1;
// 从初始状态向后转移,即 从 f[i][j][k] 开始向后转移
for(int i=0; i<n; ++i) {
for(int j=0; j<2; ++j) {
for(int k=0; k<3; ++k) {
// absent, 注意第三维置零
if(j+1 < 2)f[i+1][j+1][0] = (f[i+1][j+1][0] + f[i][j][k]) % MOD;
// late
if(k+1 < 3)f[i+1][j][k+1] = (f[i+1][j][k+1] + f[i][j][k]) % MOD;
// present, 注意第三维置零
f[i+1][j][0] = (f[i+1][j][0] + f[i][j][k]) % 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;
}
};