552. Student Attendance Record II

[흑화뉴비(coderhs)]

class Solution:

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

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

        

        def cal(cl, a, n):

            if a == 2 or cl == 3:

                return 0

            if n == 0:

                return 1

            if dp[cl][a][n] != -1:

                return dp[cl][a][n]

            ans = cal(0, a+1, n-1)

            ans += cal(cl+1, a, n-1)

            ans += cal(0, a, n-1)

            dp[cl][a][n] = ans % 1000000007

            return dp[cl][a][n]

        

        return cal(0, 0, n)

오랜만에 풀어보는 탑다운 dp 문제.