552.学生出勤记录II

链接：552.学生出勤记录II
难度：Hard
标签：动态规划
简介：给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。

题解 1 - typescript

• 编辑时间：2021-08-18
• 执行用时：2216ms
• 内存消耗：78.9MB
• 编程语言：typescript
• 解法介绍：dp[i][j][k]=第 i 天的时候存在 j 个 A 和 k 个 L 的情况。

function checkRecord(n: number): number {
  const mod = 10 ** 9 + 7;
  const dp = new Array(n + 1).fill(0).map(_ => new Array(2).fill(0).map(_ => new Array(3).fill(0)));
  dp[0][0][0] = 1;
  for (let i = 1; i <= n; i++) {
    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;
      }
    }
    for (let k = 0; k < 3; k++) {
      dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % mod;
    }
    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;
      }
    }
  }
  let ans = 0;
  for (let j = 0; j < 2; j++) for (let k = 0; k < 3; k++) ans = (ans + dp[n][j][k]) % mod;
  return ans;
}

题解 2 - python

• 编辑时间：2024-08-19
• 执行用时：690ms
• 内存消耗：16.39MB
• 编程语言：python
• 解法介绍：dp遍历。

class Solution:
    def checkRecord(self, n: int) -> int:
        # 0 末尾没有L, 共0A
        # 1 末尾没有L, 共1A
        # 2 末尾一个L, 共0A
        # 3 末尾一个L, 共1A
        # 4 末尾两个L, 共0A
        # 5 末尾两个L, 共1A
        dp = [0] * 6
        dp[0] = 1
        mod = 10 ** 9 + 7
        for _ in range(n):
            [dp[0], dp[1], dp[2], dp[3], dp[4], dp[5]] = [
                (dp[0] + dp[2] + dp[4]) % mod,
                (dp[0] + dp[1] + dp[2] + dp[3] + dp[4] + dp[5]) % mod,
                (dp[0]) % mod,
                (dp[1]) % mod,
                (dp[2]) % mod,
                (dp[3]) % mod,
            ]
        return sum(dp) % mod