摘要
Title: 552. 学生出勤记录 II
Categories: dp、记忆化搜索

552. 学生出勤记录 II

题意

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

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

思路

dfs记忆化搜索即可，但是内存占用过大，记得进行完之后进行缓存的清除 dfs.cache_clear()
枚举每一天需要填什么即可，A不能填2个以上，L不能连续3个以上

代码

'''
Author: NEFU AB-IN
Date: 2024-08-19 15:57:00
FilePath: \LeetCode\552\552.py
LastEditTime: 2024-08-19 16:06:07
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().strip())
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))
    read_mixed = staticmethod(lambda *types: [t(v) for t, v in zip(types, IO.input().split())])


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def checkRecord(self, n: int) -> int:

        @lru_cache(None)
        def dfs(day: int, ab_cnt: int, late_cnt: int):
            if day >= n:
                return 1

            res = dfs(day + 1, ab_cnt, 0)
            if ab_cnt < 1:
                res += dfs(day + 1, ab_cnt + 1, 0)
            if late_cnt < 2:
                res += dfs(day + 1, ab_cnt, late_cnt + 1)

            return res % MOD

        res = dfs(0, 0, 0) % MOD
        dfs.cache_clear()
        return res