package question0552_student_attendance_record_ii;

/**
 * 动态规划。
 *
 * 状态定义：
 * dp[i][0] 表示长度为 n，且之前没有出现过 A，之前序列最末有 0 个 L，还能组成的可奖励的出勤的数量。
 * dp[i][1] 表示长度为 n，且之前没有出现过 A，之前序列最末有 1 个 L，还能组成的可奖励的出勤的数量。
 * dp[i][2] 表示长度为 n，且之前没有出现过 A，之前序列最末有 2 个 L，还能组成的可奖励的出勤的数量。
 * dp[i][3] 表示长度为 n，且之前出现过 A，之前序列最末有 0 个 L，还能组成的可奖励的出勤的数量。
 * dp[i][4] 表示长度为 n，且之前出现过 A，之前序列最末有 1 个 L，还能组成的可奖励的出勤的数量。
 * dp[i][5] 表示长度为 n，且之前出现过 A，之前序列最末有 2 个 L，还能组成的可奖励的出勤的数量。
 *
 * 初始化条件：
 * dp[0][0] = dp[0][1] = dp[0][2] = dp[0][3] = dp[0][4] = dp[0][5] = 1。
 *
 * 状态转移方程：
 * dp[i][j] = dp[i - 1][j / 3 * 3]。
 *
 * 如果 j <= 2，dp[i][j] += dp[i - 1][3]。
 *
 * 如果 j != 2 且 j != 5，dp[i][j] += dp[i - 1][j + 1]。
 *
 * 时间复杂度和空间复杂度均是 O(n)。
 *
 * 执行用时：211ms，击败26.02%。消耗内存：49.6MB，击败100.00%
 */
public class Solution2 {
    public int checkRecord(int n) {
        int MOD = 1000000007;
        int[][] dp = new int[n + 1][6];
        for (int i = 0; i < 6; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 6; j++) {
                dp[i][j] = dp[i - 1][j / 3 * 3];
                if (j <= 2) {
                    dp[i][j] += dp[i - 1][3];
                    dp[i][j] %= MOD;
                }
                if (j != 2 && j != 5) {
                    dp[i][j] += dp[i - 1][j + 1];
                    dp[i][j] %= MOD;
                }
            }
        }
        return dp[n][0];
    }
}