题目描述

给定一个正整数 n，返回长度为 n 的所有可被视为可奖励的出勤记录的数量。 答案可能非常大，你只需返回结果mod 109 + 7的值。

学生出勤记录是只包含以下三个字符的字符串：

‘A’ : Absent，缺勤
‘L’ : Late，迟到
‘P’ : Present，到场
如果记录不包含多于一个’A’（缺勤）或超过两个连续的’L’（迟到），则该记录被视为可奖励的。

样例

输入: n = 2
输出: 8 
解释：
有8个长度为2的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励，因为缺勤次数超过一次。

算法

(动态规划) O(n)

这类题目之前没有遇到过，记录下，是多状态枚举型动态规划。
先把问题分成两部分
1. 这个n长度数列里,A出现的次数为0或者1的数列种类。
2. 这个n长度数列里,末尾连续出现L的次数的数列种类，取值范围是0，1，2。

这两个部分都有子情况可以讨论，对于第一种:

对于第1种：
1.1 数列[0:i]中没有出现过A。表示为dp0[i]
1.2 数列[0:i]中没有出现过1个A。表示为dp1[i]

dp0[i] = dp0[i - 1] * 2 (第i个位置取L,P)
dp1[i] = dp0[i - 1] * 1 (第i个位置取A) + dp1[i - 1] * 2 (第i个位置取L,P)

结果表示: dp0[n] + dp1[n]

对于第二种:

对于第2种：
数列[0:i]中最后一个字符以几个L结尾？

三部分:
2.1 dp0[i] 数列[0:i]中最后一个字符以0个L结尾的数列种类。
2.2 dp1[i] 数列[0:i]中最后一个字符以1个L结尾的数列种类。
2.3 dp2[i] 数列[0:i]中最后一个字符以2个L结尾的数列种类。

dp0[i] = (dp0[i - 1] + dp1[i - 1] + dp2[i - 1]) * 2 (第i个位置取A,P)
dp1[i] = dp0[i - 1] * 1 (第i个位置取L)
dp2[i] = dp1[i - 1] * 1 (第i个位置取L)

结果表示: dp0[n] + dp1[n] + dp2[n]

问题分成两部分都已经讨论完毕了，我们最后需要把子问题合并起来算结果：

任何一种数组排列类型，可以归结为六种状态：dp00,dp01,dp02,dp10,dp11,dp12. 状态dpij的定义是：其中i表示这个数列里A出现的次数，显然对于一个valid的数列，i的范围只能是0和1；j表示这个数列里末尾连续出现L的次数，显然对于一个valid的数列，i的范围只能是0，1，2。因此有六种状态的定义。

序列的状态就是在这六种之间转移。规律如下：

dp00[i] 表示数列[0:i]没有出现过A，且最末尾有0个L
dp01[i] 表示数列[0:i]没有出现过A，且最末尾有1个L
dp01[i] 表示数列[0:i]没有出现过A，且最末尾有2个L
dp10[i] 表示数列[0:i]出现过1个A，且最末尾有0个L
dp11[i] 表示数列[0:i]出现过1个A，且最末尾有1个L
dp12[i] 表示数列[0:i]出现过1个A，且最末尾有2个L

新状态      旧状态
dp00[i]  = dp00[i - 1] * 1 + dp01[i - 1] * 1 + dp02[i - 1] * 1

dp01[i]  = dp00[i - 1] * 1

dp02[i]  = dp01[i - 1] * 1

dp10[i]  = dp00[i - 1] * 1 + dp01[i - 1] * 1 + dp02[i - 1] * 1 + dp10[i - 1] * 1 + dp11[i - 1] * 1 + dp12[i - 1] * 1

dp11[i]  = dp10[i - 1] * 1

dp12[i]  = dp11[i - 1] * 1

当然，因为dp[i]的状态只取决于dp[i-1]，所以也可以不用设置六个一位数组，节省空间。
(我这里代码就不优化了)

Java 代码

class Solution {
    public int checkRecord(int n) {

        long[] dp00 = new long[n + 1];
        long[] dp01 = new long[n + 1];
        long[] dp02 = new long[n + 1];
        long[] dp10 = new long[n + 1];
        long[] dp11 = new long[n + 1];
        long[] dp12 = new long[n + 1];

        dp00[0] = 1;
        long mod = (long) (1E9 + 7);

        for (int i = 1; i <= n; i++) {
            dp00[i] = (dp00[i - 1] + dp01[i - 1] + dp02[i - 1]) % mod;
            dp01[i] = dp00[i - 1];
            dp02[i] = dp01[i - 1];
            dp10[i] = (dp00[i - 1] + dp01[i - 1] + dp02[i - 1] + dp10[i - 1] + dp11[i - 1] + dp12[i - 1]) % mod;
            dp11[i] = dp10[i - 1];
            dp12[i] = dp11[i - 1];
        }

        return (int) ((dp00[n] + dp01[n] + dp02[n] + dp10[n] + dp11[n] + dp12[n]) % mod);

    }
}