记录下首次独立做出困难的动态规划题
如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
按 总出勤 计，学生缺勤（
'A'）严格 少于两天。学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（
'L'）记录。
由此可知，满足条件的序列共有以下6种
序列中 0个A、在尾部连续的L个数为0，如：PP、LP
序列中 0个A、在尾部连续的L个数为1，如：PL
序列中 0个A、在尾部连续的L个数为2，如：LL
序列中 1个A、在尾部连续的L个数为0，如：PA、LA、AP
序列中 1个A、在尾部连续的L个数为1，如：AC
序列中 1个A、在尾部连续的L个数为2，如：
设dp[i][j]含义为：长度为i、且满足第j要求的序列数量
状态转移方程
dp[i+1][0] = dp[i+1][0] + dp[i+1][1] + dp[i+1][2]
由于第0个序列只有0个A、且尾部连续的L个数为0，所以其长度要增加则最后添加的元素一定是P。第0、1、2个序列在其后添加P，满足其要求。
dp[i+1][1] = dp[i+1][0]
由于第1个序列只有0个A、且尾部连续的L个数为1，所以其长度要增加则最后添加的元素一定是L。第0个序列在其后添加L，满足其要求。
dp[i+1][2] = dp[i+1][1]
由于第2个序列只有0个A、且尾部连续的L个数为2，所以其长度要增加则最后添加的元素一定是L。第1个序列在其后添加L，满足其要求。
dp[i+1][3] = dp[i+1][0] + dp[i+1][1] + dp[i+1][2] + dp[i+1][3] + dp[i+1][4] + dp[i+1][5]
由于第3个序列只有1个A、且尾部连续的L个数为0，所以其长度要增加则最后添加的元素是P或A。
第0、1、2个序列在其后添加A，满足其要求。
第3、4、5个序列在其后添加P，满足其要求。
dp[i+1][4] = dp[i+1][3]
由于第4个序列只有1个A、且尾部连续的L个数为2，所以其长度要增加则最后添加的元素一定是L。第3个序列在其后添加L，满足其要求。
dp[i+1][5] = dp[i+1][4]
由于第5个序列只有1个A、且尾部连续的L个数为2，所以其长度要增加则最后添加的元素一定是L。第4个序列在其后添加L，满足其要求。
初始化
当长度为1时，各个序列的数量为 1（P）、1（L）、0、1（A）、0、0
由于实际运算中只用两个dp数组，故使用一个一维数组作为dp，再使用一个数组存储上一个dp
class Solution {
public int checkRecord(int n) {
long[] dp = new long[]{1,1,0,1,0,0};
// 0：序列中0A 尾部连续L个数0, 可加p
// 1：序列中0A 尾部连续L个数1, 可加L
// 2：序列中0A 尾部连续L个数2, 可加L
// 3：序列中1A 尾部连续L个数0, 可加A、P
// 4：序列中1A 尾部连续L个数1, 可加L
// 5：序列中1A 尾部连续L个数2, 可加L
long[] t = new long[]{1,1,0,1,0,0};// 临时存储
long m = 1000000000 + 7;
for(int i = 2;i<=n;i++){
dp[0] = (t[0] + t[1] + t[2])%m;
dp[1] = t[0]%m;
dp[2] = t[1]%m;
dp[3] =( t[0] + t[1] + t[2] + t[3]+ t[4] + t[5])%m;
dp[4] = t[3]%m;
dp[5] = t[4]%m;
for(int j=0;j<6;j++)
t[j] = dp[j];
}
long sum=0;
for(int i=0;i<6;i++)
sum = (sum + dp[i])%m;
return (int)sum;
}
}也是难绷，考完研后数学就再没碰过（也不想碰），根本想不到官方题解还能再将其转化为矩阵相乘、再来个矩阵快速幂。