552. Student Attendance Record II - Explanation

class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 1000000007
        cache = [[[-1 for _ in range(3)] for _ in range(2)] for _ in range(n + 1)]

        def dfs(i, cntA, cntL):
            if i == 0:
                return 1
            if cache[i][cntA][cntL] != -1:
                return cache[i][cntA][cntL]

            res = dfs(i - 1, cntA, 0) % MOD

            if cntA == 0:
                res = (res + dfs(i - 1, 1, 0)) % MOD

            if cntL < 2:
                res = (res + dfs(i - 1, cntA, cntL + 1)) % MOD

            cache[i][cntA][cntL] = res
            return res

        return dfs(n, 0, 0)

class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 10**9 + 7
        cache = {}

        def count(n):
            if n == 1:
                # (A, L)
                return {
                    (0, 0): 1, (0, 1): 1, (0, 2): 0,
                    (1, 0): 1, (1, 1): 0, (1, 2): 0
                }

            if n in cache:
                return cache[n]

            tmp = count(n - 1)
            res = defaultdict(int)

            # Choose P
            res[(0, 0)] = ((tmp[(0, 0)] + tmp[(0, 1)]) % MOD + tmp[(0, 2)]) % MOD
            res[(1, 0)] = ((tmp[(1, 0)] + tmp[(1, 1)]) % MOD + tmp[(1, 2)]) % MOD

            # Choose L
            res[(0, 1)] = tmp[(0, 0)]
            res[(0, 2)] = tmp[(0, 1)]
            res[(1, 1)] = tmp[(1, 0)]
            res[(1, 2)] = tmp[(1, 1)]

            # Choose A
            res[(1, 0)] += ((tmp[(0, 0)] + tmp[(0, 1)]) % MOD + tmp[(0, 2)]) % MOD

            cache[n] = res
            return res

        return sum(count(n).values()) % MOD

class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 1000000007
        dp = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(n + 1)]

        dp[0][0][0] = 1  # Base case

        for i in range(1, n + 1):
            for cntA in range(2):
                for cntL in range(3):
                    # Choose P
                    dp[i][cntA][0] = (dp[i][cntA][0] + dp[i - 1][cntA][cntL]) % MOD

                    # Choose A
                    if cntA > 0:
                        dp[i][cntA][0] = (dp[i][cntA][0] + dp[i - 1][cntA - 1][cntL]) % MOD

                    # Choose L
                    if cntL > 0:
                        dp[i][cntA][cntL] = (dp[i][cntA][cntL] + dp[i - 1][cntA][cntL - 1]) % MOD

        return sum(dp[n][cntA][cntL] for cntA in range(2) for cntL in range(3)) % MOD

class Solution:
    def checkRecord(self, n: int) -> int:
        if n == 1:
            return 3

        MOD = 10**9 + 7
        dp = {
            (0, 0): 1, (0, 1): 1, (0, 2): 0,
            (1, 0): 1, (1, 1): 0, (1, 2): 0
        }

        for i in range(n - 1):
            ndp = defaultdict(int)

            # Choose P
            ndp[(0, 0)] = ((dp[(0, 0)] + dp[(0, 1)]) % MOD + dp[(0, 2)]) % MOD
            ndp[(1, 0)] = ((dp[(1, 0)] + dp[(1, 1)]) % MOD + dp[(1, 2)]) % MOD

            # Choose L
            ndp[(0, 1)] = dp[(0, 0)]
            ndp[(1, 1)] = dp[(1, 0)]
            ndp[(0, 2)] = dp[(0, 1)]
            ndp[(1, 2)] = dp[(1, 1)]

            # Choose A
            ndp[(1, 0)] = (ndp[(1, 0)] + (((dp[(0, 0)] + dp[(0, 1)]) % MOD + dp[(0, 2)]) % MOD)) % MOD

            dp = ndp

        return sum(dp.values()) % MOD

class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 1000000007
        dp = [[0] * 3 for _ in range(2)]

        dp[0][0] = 1  # Base case

        for i in range(1, n + 1):
            next_dp = [[0] * 3 for _ in range(2)]

            for cntA in range(2):
                for cntL in range(3):
                    # Choose P
                    next_dp[cntA][0] = (next_dp[cntA][0] + dp[cntA][cntL]) % MOD

                    # Choose A
                    if cntA > 0:
                        next_dp[cntA][0] = (next_dp[cntA][0] + dp[cntA - 1][cntL]) % MOD

                    # Choose L
                    if cntL > 0:
                        next_dp[cntA][cntL] = (next_dp[cntA][cntL] + dp[cntA][cntL - 1]) % MOD

            dp = next_dp

        return sum(dp[cntA][cntL] for cntA in range(2) for cntL in range(3)) % MOD