Python 3: TC O(N), SC O(N): Dynamic Programming with "rollMax Correction"
Intuition\n\nMy first attempt (commented out) was a VERY brute-force top-down DFS solution. It works, but is fairly slow. Vastly slower than this solution. The 
# Intuition\n\nMy first attempt (commented out) was a VERY brute-force top-down DFS solution. It works, but is fairly slow. Vastly slower than this solution. The reason is it\'s not very clever about avoiding the max sequence length.\n\nSo I looked at some other solutions and didn\'t understand for a while.\n\nHere\'s the major insight:\n\nFirst, suppose we know the number of *valid* sequences of `r` rolls that end with `k = 1..6`. We\'ll call it `dp[r][k]`, not to be confused with the equally glorious DPRK.\n\nThe total number of ways to end with `k` after `r` rolls are:\n* we can do `r-1` rolls that end with 1, then roll `k`: `dp[r-1][1]`\n* or we can do `r-1` rolls ending with 2, then roll `k`: `dp[r-1][1]`\n* and so on\n\n**So the total ways is `dp[r][k] = dp[r-1][1] + .. + dp[r-1][6]`. To simplify that, let\'s call that sum of `dp[r][*] == s[r]`. `s` for "sum."**\n\nBut this total includes rolling `k` `rollMax[k]+1` times in a row. So **we need to correct for (i.e. subtract) the ways to roll `k` `rollMax[k]+1` times in a row.**\n\nNow here\'s the trick: how many ways can you do `r` rolls where the last `rollMax[k]+1` are all `k`?\n\nLooks hard, but the answer is actually very similar to the total ways formula. Let `f = r-(rollMax[k]+1)`, the number of rolls before rolling `rollMax[k]+1` `k`\'s in a row. The ways to do `r` rolls ending with `rollMax[k]+1` `k`\'s in a row is:\n* **do `f` rolls, ending with any number EXCEPT `k`**\n  * `s[f] - dp[f][k]`\n* **then roll `rollMax[k]+1` `k`\'s in a row:** there\'s `1` way: all `k`\'s\n* so the total number of invalid sequences is `s[f] - dp[f][k]`\n\n**And thus the answer is `dp[r][k] = s[r-1] - (s[f] - dp[f][k])`.** This is all ways, minus all invalid ways.\n\n# Approach\n\nWe could (and probably should) have separate tables for `dp[r][k]` and `s[r]`. But I was inspired by the solutions to be really clever and store everything in one table.\n\nMoreover, the `k` above are 1-indexed, but the `rollMax` array is 0-indexed.\n\nSo I did the following, inspired by other solutions:\n* make `dp[r][k]` the ways to end `r` rolls with `k+1`\n* make `dp[r][6]` be `s[r]`, the sum of `dp[r][0] + .. + dp[r][5]`\n\nThe last detail is what happens when `f == 0`, or `r == rollMax[k]+1`. Then if you\'re not careful, the correction subtracts 0 instead of 1\n* the first row of the table is all zeros because you can\'t roll 0 dice\n* but there is really 1 way to roll all `k`\'s\n\nThe subtraction is fixed by making a quick hack to the table: `dp[0][-1] = 1`. This way the `-(s[f] - dp[f][k])` correction is `-1` when `f == 0`.\n\n# Complexity\n- Time complexity: O(N)\n\n- Space complexity: O(N)\n\n# Possible Space Optimization\n\nWe know that we only need to go back `rollMax[k]+1` rows to get the correction. So we really only need about `max(rollMax)` rows in the table.\n\nAn easy-ish way to do it would be to make a table with about `max(rollMax)+2` rows, and have a pointer to the current index in that shorter table. Then we can use modular arithmetic to get the index of `r` in the shorter table.\n\nIn other words, basically make the table be a ring buffer of rows.\n\n# Code\n```\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # # # no more than rollMax consec. times\n\n        # # # probably a DP question...\n        # # # suppose I know C[k], the count of sequences with k consecutive ones\n\n        # # # then from C[k] we can roll\n        # # #    1 in one way: -> C[k+1]\n        # # #   !1 in five ways -> C[0]\n\n        # # # and so C[k] after the roll is the sum of C[k-1] for k >= 1\n        # # # and C[0] = 5*sum(C[k]) for all k\n\n        # # # we can be REALLY clever and do some in-place stuff\n        # # # but here we\'ll just "toggle" a prev/curr state\n        # # BIG = 10**9+7\n        # # prev = [0]*(rollMax+1)\n        # # prev[0] = 5\n        # # prev[1] = 1 # state after 1 roll\n        # # curr = [0]*(rollMax+1)\n        # # for _ in range(n-1):\n        # #     for k in range(1, rollMax+1):\n        # #         curr[k] = prev[k-1] # only one way: ...1{k-1} -[1]-> ...1{k}\n        # #     curr[0] = 5*sum(prev) % BIG # for any number of trailing 1s, we can roll 2..6 to get 0 trailing\n\n        # #     curr, prev = prev, curr\n\n        # # return sum(prev) % BIG\n\n\n        # ##### oh no... it\'s a separate max for each number!!\n        # ## DP would be really annoying, but doable - relatively giant table\n        # #   with all number of trailing counts for each die. Oof.\n\n        # m1, m2, m3, m4, m5, m6 = rollMax\n        # BIG = 10**9 + 7\n\n        # # actual number of states is lower, there are 1..mk missing from any one k\n        # # so the complexity is O(S*n) where s = sum(rollMax)\n\n        # # top-down DFS makes this a LOT easier\n        # @cache\n        # def ways(n: int, r1: int, r2: int, r3: int, r4: int, r5: int, r6: int) -> int:\n        #     """Returns ways to roll `n` dice given we can roll rk more rolls of k"""\n\n        #     if n == 1:\n        #         return bool(r1) + bool(r2) + bool(r3) + bool(r4) + bool(r5) + bool(r6)\n\n        #     ans = 0\n        #     if r1: ans += ways(n-1, r1-1, m2, m3, m4, m5, m6)\n        #     if r2: ans += ways(n-1, m1, r2-1, m3, m4, m5, m6)\n        #     if r3: ans += ways(n-1, m1, m2, r3-1, m4, m5, m6)\n        #     if r4: ans += ways(n-1, m1, m2, m3, r4-1, m5, m6)\n        #     if r5: ans += ways(n-1, m1, m2, m3, m4, r5-1, m6)\n        #     if r6: ans += ways(n-1, m1, m2, m3, m4, m5, r6-1)\n        #     return ans % BIG\n\n        # return ways(n, m1, m2, m3, m4, m5, m6)\n\n        # Something about\n        #    > suppose we want to avoid rolling more than 3 6\'s in a row\n        #    > and we\'re looking at roll 8\n        #    > then we can apparently determine all the valid ways just from the ways to\n        #      roll sequences with any number of each number\n\n        # dp[r][k] is number of sequences after r rolls that end with k\n\n        # dp[r][k] = dp[r-1][0] + .. + dp[r-1][5] == dp[r][-1]; store sum of each row in last element\n        #  is mostly right, but it includes (possibly) 3-in-a-row sixes\n        #  ways to get 1 6 in a roll after r: roll r-1 times, then add a 6 to each non-six-terminated squence:\n        #     dp[r][5] = dp[r-1][0] + .. + dp[r-1][4] = dp[r-1][-1] - dp[r-1][5]\n        #  ways to get 2 6 in a roll after r: roll r-2 times, ending with another number, then roll 6 twice:\n        #     dp[r-2][-1] - dp[r-2][5]\n        #  ways to roll k+1 in row: dp[r-k-1][-1] - dp[r-k-1][5]\n\n        BIG = 10**9 + 7\n\n        dp = [[0]*7 for _ in range(n+1)]\n        for k in range(6):\n            dp[1][k] = 1\n        dp[1][-1] = 6\n        dp[0][-1] = 1 # FIX, see below, this way the "rollMax" correction\n                      #      is correct for f==0\n\n        for r in range(2, n+1):\n            for k in range(6):\n                dp[r][k] = dp[r-1][-1]\n                if r > rollMax[k]:\n                    # subtract off ways to roll rollMax[k]+1 rolls of k in a row\n                    # the ways to do that are\n                    # roll r-(rollMax+1) of anything *except* k\n                    # then roll k  rollMax+1 times in a row\n\n                    # FIX: if f == 0 we subtracted 0 before\n                    #      but that\'s wrong of course because there\'s 1 way\n                    #      to roll all k\'s. So we set dp[0][-1] to 1 as a kind of guard element\n                    f = r-rollMax[k]-1\n                    dp[r][k] -= (dp[f][-1] - dp[f][k])\n\n                dp[r][-1] += dp[r][k]\n\n            dp[r][-1] %= BIG\n\n        return dp[n][-1]\n```
['Python3']