content: 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];
      }
  }