[Python] DP thought process and solution
The memoized version is quite straightforward so please refer to other posts. The DP version is very tricky and requires a bit of thinking and some math to get 
The memoized version is quite straightforward so please refer to other posts. The DP version is *very* tricky and requires a bit of thinking and some math to get it provably correct. \n\nTo make the code easier to follow, let\'s assume the die values are [0, 1, 2, 3, 4, 5]. \nThe values are arbitrary as long as there are 6 distinct values so this doesn\'t affect the problem. (And rollMax is 0-index based anyways so this is perfect)\n\nImagine we are on roll r, 1 <= r <= n, and we\'ve landed on the die value x, 0 <= x <= 5. And let\'s assume we are allowed maximum, k = rollMax[x], consecutive rolls of x. Then for this to be a valid roll sequence, it must have been one of the following sequences (where y can be any die value other than x):\n\n<pre>\n  .........yx   (sequence with 1 consecutive x)\n  ........yxx   (sequence with 2 consecutive x)\n  .......yxxx   (sequence with 3 consecutive x)\n  ...\n  ...\n  ....yx....x   (sequence with k consecutive x)\n  </pre>\n\nLet\'s define f(r, x) to be the number of valid sequences with exactly r rolls such that the last roll lands on die value x.\n<pre>\n   f(r, x) =   sigma(for all y!=x)[f(r - 1, y)] \n             + sigma(for all y!=x)[f(r - 2, y)] \n             + ... \n             + sigma(for all y!=x)[f(r - k, y)]\n</pre>\n\nwell notice that:\n <pre>sigma(for all y!=x)[f(r - j, y)] = sigma(v = [0..5])[f(r - j, v)] - f(r - j, x)</pre>\n  In other words, all possible sequences after exactly r-j rolls ending at any die value y other than x, is all possible sequences ending at any value v, excluding those ending at x.\n\nThen we have:\n<pre>\n  f(r, x) =   sigma(v = [0..5])[f(r - 1, v)] - f(r - 1, x)\n            + sigma(v = [0..5])[f(r - 2, v)] - f(r - 2, x)\n            + ...\n            + sigma(v = [0..5])[f(r - k, v)] - f(r - k, x)\n           </pre>\n\n  Let\'s define g(r - i) = sigma(v = [0..5])[f(r - i, v)], then:\n<pre>\n  f(r, x) =   g(r - 1) - f(r - 1, x)\n            + g(r - 2) - f(r - 2, x)\n            + ...\n            + g(r - k) - f(r - k, x)\n</pre>\nWe also define special sentinel values to make it easy to build the dp table bottom-up:\n<pre>\n  f(0, x) = 0, for any x. Because it\'s not possible to land on some specific value x without having \n               rolled something.\n  g(0) = 1, because the empty, zero-th, roll is 1 possible sequence.\n </pre>\n\nNow the code writes itself.\n\n```\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        if n <= 0:\n            return 0\n        \n        f = [None] * (n + 1)\n        f[0] = [0] * 6\n        g = [0] * (n + 1)\n        g[0] = 1\n        for r in range(1, n + 1):\n            f[r] = [0] * 6\n            for x in range(6):\n                for k in range(1, rollMax[x] + 1):\n                    if r - k >= 0:\n                        f[r][x] += g[r-k] - f[r-k][x]\n                g[r] += f[r][x]\n        \n        return g[n] % (10**9 + 7)\n```
[]