题目描述
思路
动态规划
代码

552. 学生出勤记录 II

August 18, 2021

题目描述

可以用字符串表示一个学生的出勤记录,其中的每个字符用来标记当天的出勤情况(缺勤、迟到、到场)。记录中只含下面三种字符:
'A':Absent,缺勤
'L':Late,迟到
'P':Present,到场
如果学生能够 同时 满足下面两个条件,则可以获得出勤奖励:

按 总出勤 计,学生缺勤('A')严格 少于两天。
学生 不会 存在 连续 3 天或 连续 3 天以上的迟到('L')记录。
给你一个整数 n ,表示出勤记录的长度(次数)。请你返回记录长度为 n 时,可能获得出勤奖励的记录情况 数量 。答案可能很大,所以返回对 109 + 7 取余 的结果。

 

示例 1:

输入:n = 2
输出:8
解释:
有 8 种长度为 2 的记录将被视为可奖励:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励,因为缺勤次数为 2 次(需要少于 2 次)。
示例 2:

输入:n = 1
输出:3
示例 3:

输入:n = 10101
输出:183236316
 

提示:

1 <= n <= 105


来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/student-attendance-record-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

动态规划

定义状态 dp[i][j][k] 为前 i 个位置前使用 j 个’A’末尾为连续 k 个’L’的合法串数量,其中 (0 <= j <= 1, 0 <= k <=2), 则有状态方程

  • 末尾加 P dp[i][j][0] = dp[i][j][0] + dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2] dp[i][j][1] = 0 dp[i][j][2] = 0
  • 末尾加 A dp[i][1][0] = dp[i][j][0] + dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2] dp[i][1][1] = 0 dp[i][1][2] = 0
  • 末尾加 L dp[i][j][k] = dp[i][j][k] + dp[i-1][j][k-1]

代码

/**
 * @param {number} n
 * @return {number}
 */
var checkRecord = function (n) {
  const mod = 10 ** 9 + 7;
  let dp = Array.from({ length: n + 1 }).map((_) =>
    Array.from({ length: 2 }).map((_) => Array.from({ length: 3 }).fill(0))
  );

  dp[0][0][0] = 1;

  for (let i = 1; i <= n; i++) {
    // 前一个序列结尾补P
    for (let j = 0; j < 2; j++) {
      for (let k = 0; k < 3; k++) {
        dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % mod;
      }
    }

    // 前一个序列结尾补 A
    for (let k = 0; k < 3; k++) {
      dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % mod;
    }

    // 前一个序列结尾补 L
    for (let j = 0; j < 2; j++) {
      for (let k = 1; k < 3; k++) {
        dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % mod;
      }
    }
  }

  // sum
  let sum = 0;
  for (let i = 0; i < 2; i++) {
    for (let j = 0; j < 3; j++) {
      sum = (sum + dp[n][i][j]) % mod;
    }
  }

  console.log({ sum });
  return sum;
};

checkRecord(1);
checkRecord(2);
  • 时间复杂度: $O(N * 2 * 3)$
  • 空间复杂度: $O(N * 2 * 3)$

feiker 少年起而行之