552.学生出勤记录-ii.md

552.学生出勤记录-ii

/*
 * @lc app=leetcode.cn id=552 lang=typescript
 *
 * [552] 学生出勤记录 II
 */

// @lc code=start
function checkRecord(n: number): number {}
// @lc code=end

解法 1: 动态规划

1. 子问题: 第 i 天能获得出勤奖的数量
2. 状态:
   • dp[i][j]: 表示第 i 天缺勤状态为 j ,迟到次数为 k 能获得出勤奖的数量
   • 未缺勤: j=0
     • 到场: dp[i][j][0]
     • 迟到 1 次: dp[i][j][1]
     • 迟到 2 次: dp[i][j][2]
   • 缺勤: j=1
     • 缺勤: dp[i][j][0]
     • 迟到 1 次: dp[i][j][1]
     • 迟到 2 次: dp[i][j][2]
3. DP 方程:
   • dp[i][j][0] = dp[i-1][j][2] + dp[i-1][j][1] + dp[i-1][j][0] + dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]
   • dp[i][j][1] = dp[i-1][j][0]
   • dp[i][j][2] = dp[i-1][j][1]
4. 边界
   • dp[0]=[[0,0,0],[1,1,0],[1,0,0]]
   • dp[i][0]=[0,0,0]

function checkRecord(n: number): number {
  const MOD = 1e9 + 7

  const dp = [
    [
      [0, 0, 0],
      [1, 1, 0],
      [1, 0, 0],
    ],
  ]
  for (let i = 1; i < n; i++) {
    dp[i] = [[0, 0, 0], [], []]
    for (let j = 1; j < 3; j++) {
      dp[i][j][0] =
        (dp[i - 1][j][2] +
          dp[i - 1][j][1] +
          dp[i - 1][j][0] +
          dp[i - 1][j - 1][0] +
          dp[i - 1][j - 1][1] +
          dp[i - 1][j - 1][2]) %
        MOD
      dp[i][j][1] = dp[i - 1][j][0] % MOD
      dp[i][j][2] = dp[i - 1][j][1] % MOD
    }
  }

  return [...dp[n - 1][1], ...dp[n - 1][2]].reduce((a, b) => (a + b) % MOD)
}

解法 2: 空间优化

• 未缺勤: p
• 未缺勤迟到 1 次: l
• 未缺勤迟到 2 次: l2
• 缺勤 1 次: a
• 缺勤 1 次,迟到 1 次: al
• 缺勤 1 次,迟到 2 次: al2

function checkRecord(n: number): number {
  const MOD = 10 ** 9 + 7
  let [p, l, l2, a, al, al2] = [1, 1, 0, 1, 0, 0]
  for (let i = 2; i <= n; i++) {
    ;[p, l, l2] = [(p + l + l2) % MOD, p, l]
    ;[a, al, al2] = [(p + a + al + al2) % MOD, a, al]
  }
  return [p, l, l2, a, al, al2].reduce((a, b) => (a + b) % MOD)
}

Case

test.each([
  { input: { n: 1 }, output: 3 },
  { input: { n: 2 }, output: 8 },
  { input: { n: 3 }, output: 19 },
  { input: { n: 6 }, output: 200 },
  { input: { n: 10 }, output: 3536 },
  { input: { n: 10101 }, output: 183236316 },
])(`input: n = $input.n`, ({ input: { n }, output }) => {
  expect(checkRecord(n)).toBe(output)