Short Python DP with detailed image explanation
Here I illustrate the idea with the example: Input: n = 3, rollMax = [1,1,1,2,2,3]. Output: 181.\n\nAlso the definition of DP array:\n- for j = 0, 1, ..., faces
Here I illustrate the idea with the example: Input: n = 3, rollMax = [1,1,1,2,2,3]. Output: 181.\n\nAlso the definition of DP array:\n- for `j = 0, 1, ..., faces - 1`\n\t- `dp[i][j]` means how many combinations it could be that at `i-th` rolling and the last face is `j`\n- for `j = faces`\n\t- `dp[i][j]` means how many combinations it could be that at `i-th` rolling in total\n\nBasically on every `[i][j]`, we are trying to climb up in the column `[j]`, and how many steps we could climb up is based on `rollMax[j]`.\n\n\n![image](https://assets.leetcode.com/users/zzzliu/image_1571040537.png)\n\n\n------\nAnother example: let\'s say we roll dice `i = 5` times, and the last face is `j = 5`, then we have this sequence `xxxx5` where `x` could ranges from `0` to `5` arbitrarily if we are not restricted. Then let\'s calculate how many combinations we could form `xxxx5` with constraint `rollMax[j] = 3`. They could be categorized as follow:\n1. step1: `xxxy5`, where x in `[0, 5]` and y in `[0, 4]`, this means from the end `5`, we have consecutive one `5`\n2. step2: `xxy55`, this means from the end `5`, we have consecutive two `5`\n3. step3: `xy555`, this means from the end `5`, we have consecutive three `5`\n4. We could not climb the column upper because we are restricted to only be able to climb up `rollMax[j] = 3` steps.\n\nThen the question is how to calculate the combinations of `...xy`. Actually if you take a deeper look, what `...xy` means is essentially: give me all the combinations as long as the last face is not 5. We don\'t care what `x` should be here because it is not restricted and could choose any value (it could be even same as `y`, or same as `5`). As long as `y` is not equal to `5`, we are good to go. And that is the definition `dp[i][j]`!\n\n```\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007\n        \n```
[]