↓Skip to main content
  1. Posts/

LeetCode-552 学生出勤记录 II

·1 min·
Table of Contents

LeetCode-552 学生出勤记录 II #

Solution 1 #

字符串的关键状态在于 'A' 字符的个数以及结尾连续 'L' 的个数. 枚举结尾的字符进行动态规划.

代码如下:

class Solution:
    def checkRecord(self, n: int) -> int:
        mod = 1_000_000_007

        dp = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(n)]
        dp[0][0][0] = 1
        dp[0][0][1] = 1
        dp[0][1][0] = 1

        for i in range(1, n):
            dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % mod
            dp[i][0][1] = dp[i - 1][0][0]
            dp[i][0][2] = dp[i - 1][0][1]
            dp[i][1][0] = (dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2] + dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % mod
            dp[i][1][1] = dp[i - 1][1][0]
            dp[i][1][2] = dp[i - 1][1][1]
            
        ans = 0
        for j in range(2):
            for k in range(3):
                ans = (ans + dp[n - 1][j][k]) % mod
        return ans