[Python3] top-down dp
Algo\nDefine fn(n, x, r) as the number of sequences with n rolls left and r occurrences of x just now. \n\nImplementation\n\nclass Solution:\n    def dieSimulat
**Algo**\nDefine `fn(n, x, r)` as the number of sequences with `n` rolls left and `r` occurrences of `x` just now. \n\n**Implementation**\n```\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        @cache\n        def fn(n, x, r):\n            """Return number of sequences with n rolls left with r occurrences of x."""\n            if n == 0: return 1\n            ans = 0\n            for xx in range(6): \n                if xx != x: ans += fn(n-1, xx, 1)\n                elif xx == x and r < rollMax[x]: ans += fn(n-1, x, r+1)\n            return ans \n        \n        return sum(fn(n-1, x, 1) for x in range(6)) % 1_000_000_007\n```\n\n**Analysis**\nTime complexity `O(NK)`\nSpace complexity `O(NK)`
['Python3']