Python from O(6^n) backtrack to O(N^2) memorization step by step
\n"""\nsolution 1: backtrack - O(6^N) in worst case\n"""\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def backtrack
```\n"""\nsolution 1: backtrack - O(6^N) in worst case\n"""\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def backtrack(curr_roll, curr_comb):\n            if curr_roll == n:\n                self.res += 1\n                return\n            \n            for num in [1, 2, 3, 4, 5, 6]:\n                if len(curr_comb) >= rollMax[num-1] and \\\n                all(cons_num == num for cons_num in curr_comb[-rollMax[num-1]:]):\n                    continue      \n                curr_comb.append(num)\n                backtrack(curr_roll + 1, curr_comb)\n                curr_comb.pop()\n                \n        \n        self.res = 0\n        backtrack(0, [])\n        return self.res\n        \n        \n"""\nsolution 1: a little modified backtrack - O(6^N) in worst case.\n"""\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def backtrack(curr_roll, last_num, repeat_time):\n            """\n            we only need last_num and the repeat time of last_num\n            """\n            if curr_roll == n:\n                self.res += 1\n                return\n            \n            for num in [1, 2, 3, 4, 5, 6]:\n                if num == last_num:\n                    if repeat_time >= rollMax[num-1]:     \n                        continue                        \n                    backtrack(curr_roll + 1, num, repeat_time + 1)\n                else:\n                    backtrack(curr_roll + 1, num, 1)\n                \n        \n        self.res = 0\n        backtrack(0, -1, -1)    \n        return self.res\n        \n        \n"""\nsolution 2: backtrack + memo - O(n^2).\n"""\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def backtrack(curr_roll, last_num, repeat_time):\n            if (curr_roll, last_num, repeat_time) in memo:\n                return memo[(curr_roll, last_num, repeat_time)]\n            \n            if curr_roll == n:\n                return 1\n            if curr_roll > n:\n                return 0\n            \n            res = 0\n            for num in [1, 2, 3, 4, 5, 6]:\n                if num == last_num:\n                    if repeat_time >= rollMax[num-1]:     \n                        continue                       \n                    res = (res + backtrack(curr_roll + 1, num, repeat_time + 1) % MOD) % MOD \n                else:\n                    res = (res + backtrack(curr_roll + 1, num, 1) % MOD) % MOD\n            \n            memo[(curr_roll, last_num, repeat_time)] = res\n            return res\n                \n        \n        MOD = 10**9 + 7\n        memo = collections.defaultdict(int)     # (curr_roll, last_num, repeat_time) --> how many ways\n        return backtrack(0, 0, 0)    \n```
['Backtracking', 'Memoization', 'Python3']