Commented Python 3 Short Solution
Wow, this was a tricky problem; took me many hours. Here\'s how I thought about it. Hopefully it doesn\'t seem too convoluted, or if it does, there\'s still som
Wow, this was a tricky problem; took me many hours. Here\'s how I thought about it. Hopefully it doesn\'t seem too convoluted, or if it does, there\'s still some inutiton here for those struggling.\n\n**- The Plan -**\n\nWe need to build an array representing the number of ways I can roll each side of a die as the N-th roll. The sum of the entires in this array will contain the solution.\n\nWe can build this up by examining the aggregate of rolls on the i-th iteration of making the desired array.\n\nAssume we have the correct answer thus far; we know the number of paths leading to rolling *this* dice-face on *this* iteration of rolling. That is, we hone in on a single square. \n\n**- Visual -**\n\nPicture a bundle of paths leading to the current square. If the bundle of paths continue down the path of the same dice-face, they will eventually terminate due to rollMax for that dice-face. If they re-route to a different dice-face, those routes can propagate forward. The totality of all the routes (for each numbered square) at a particular iteration gets you all the routes leading to that iteration.\n\n**- The Long Explanation -**\n\nThe intuition: we know that the number of paths leading to this square will only be propagated  ```rollMax[dice_face]``` number of times forward along the same dice-face rolls before we end up exceeding the maximum chain of dice-faces in a row. Therefore, all paths that lead to the current-roll on this iteration will be invalid *specifically* at ``` current_iteration + rollMax[dice_face]``` number of iterations in the future with the same dice_face, not before (have not yet reached max), not after (have reset with some different roll). I call this a **\'projection**\'. This number of invalid paths should be recorded in this future square, and this number should affect the sum along the column (ways to arrive at the current iteration).\n\nThe next consideration I find the trickiest; maybe someone has a better explanation?\n\nThere may also be invalid paths recorded with the same dice-face before we "reach" the projection (e.g. ```rollMax[dice_face] === 3``` ... => current  =>  -20 =>  -40   =>  projection). We have to remove these from the number of invalid paths at the projection site, because these intermediary projections are only invalid coming from the same dice-side (along the same chain); other paths will start with the current square, go to another dice-side, then come back to the initial dice-side. This means that these paths have a route to projection site and should be accounted for. Removing the entirety of the number of paths leading to the current iteration at the future projection would remove too many paths.\n\nFrom here, you just sum up the column, add the sum to the entries in the next column, and repeat the projection process. Figure out the case at the first roll, and your program is all set.\n\n**- Solution -**\n\n```\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        DICE_SIDES = len(rollMax)\n        \n        # Table squares contain the number of possible ith-long paths leading to this specific dice-roll\n        table = [[0 for _ in range(DICE_SIDES)] for _ in range(n)]\n        table[0] = [1 for _ in range(DICE_SIDES)]\n        ways_to_arrive = 0\n        \n        for ith_roll in range(n):\n            for dice_side in range(DICE_SIDES):\n                # The square will contain the number of "invalid paths" as a negative number\n                # as a result of the work done with projected rolls\n                table[ith_roll][dice_side] += ways_to_arrive\n                \n                # Consider creating one long chain of the same dice-side roll starting from the current square\n                projected_roll = ith_roll + rollMax[dice_side]\n                if projected_roll < n:\n                    # The invalid counts along the way are only invalid for the specific projection;\n                    # They are valid for all subsequent rolls of the same dice-side\n                    invalid_before_projected = sum(table[i][dice_side] for i in range(ith_roll+1, projected_roll))\n                    table[projected_roll][dice_side] = -table[ith_roll][dice_side] - invalid_before_projected\n            ways_to_arrive = sum(table[ith_roll])\n        \n        return ways_to_arrive % (10**9 + 7)\n                    \n```
[]