Python DP with image explanation
\n\ndp[i][j] := the i-th valid rolls that end with rolling out (j + 1)\ndp[i][6]:= the sum of dp[i][0] + ... + dp[i][5] \n\nIn the image, we want to find out dp
![image](https://assets.leetcode.com/users/codingasiangirll/image_1586550246.png)\n\n`dp[i][j]` := the `i`-th valid rolls that end with rolling out (`j` + 1)\n`dp[i][6]`:= the sum of `dp[i][0]` + ... + `dp[i][5]` \n\nIn the image, we want to find out `dp[8][5]`, which is the 8-th roll that end with rolling out #6, and we also know that `rollMax[5]`= 3.\n1. Valid sequences will be result of valid sequences that are generated at 7-th roll (`dp[i - 1][-1]`, sum1 in the diagram) and the invalid cases that should be exluded. \n2. Invalid cases here is rolling out #6 at 5-th(`k`), 6-th, and 7-th roll. Then At the 8-th roll it can never have rolled out #6. The number of invalid cases can be derived from all valid sequences of `k - 1`-th roll that are not ending with #6 (`dp[k - 1][-1]`, sum2 in the diagram - `dp[k - 1][j]`).\n\nBased on 1 and 2, we can get the transition functions:\n`k = i - rollMax[j]`\n`dp[i][j] = dp[i - 1][-1] - (dp[k - 1][-1] - dp[k - 1][j])`\n```\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]\n        for j in range(len(rollMax)):\n            dp[1][j] = 1\n            dp[1][-1] += dp[1][j]\n        \n        for i in range(2, n + 1):\n            for j in range(len(rollMax)):\n                dp[i][j] = dp[i - 1][-1]\n                k = i - rollMax[j]\n                if k == 1:\n                    dp[i][j] -= 1\n                elif k > 1:\n                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])\n                dp[i][-1] += dp[i][j]\n        return dp[n][len(rollMax)] % int(1e9 + 7)\n        \n```
['Dynamic Programming']