[Python] Easy DP solution with detailed explanation
To solve it using dynamic programming, let\'s first figure out how many states we need to track. Without the constraint, apparently there are 6 states correspon
To solve it using dynamic programming, let\'s first figure out how many states we need to track. Without the constraint, apparently there are 6 states corresponding to 1, 2, ..., 6 numbers on a dice. Since the constraint indicates how many consecutive times one number can be generated, one number can be associated with multiple states. For example, if the constraint indicates the number `1` can only be generated no more than `3` consecutive times, the 3 different states associated with `1` are  `the first 1`, `the second 1` and `the third 1` in a consecutive sequence of `1`s. Therefore, in total there are `sum(rollMax) * 6` states. Let\u2019s use ` dp = [[0] * x for x in rollMax]` to store the number of sequences for each state.\n\nAfter figuring out the states, let\u2019s try to find the state transition functions. Let\u2019s also use number `1` with rollMax `3` as an example. There are 3 cases here:\n1. It is the first time `1` is generated consecutively\n2. It is the second time `1` is generated consecutively\n3. It is the third time `1` is generated consecutively\n\nFor case 1, we just need to sum up all the number of different sequences in the previous step where number `1` is not generated to get the number of sequence for current state.\nFor case 2, since it is the second time `1` is generated consecutively, we only need to use the number of sequences in the previous step where number `1` is generated for the first time to populate the current state. \nCase 3 is similar to case 2.\n\n```\n        dp = [[0] * x for x in rollMax]\n\t\t# initialize dp\n        for k in range(6):\n            dp[k][0] = 1\n        for k in range(1, n):\n            next_dp = [[0] * n for n in rollMax]\n            roll_sum = [sum(x) for x in dp]\n            total = sum(roll_sum)            \n            for i in range(6):\n                for j in range(rollMax[i]):\n                    if j == 0:\n                        next_dp[i][j] = total - roll_sum[i] % (10**9 + 7)\n                    else:\n                        next_dp[i][j] = dp[i][j-1] % (10**9 + 7)\n            dp = next_dp\n        return sum([sum(x) for x in dp]) % (10**9 + 7)\n```
[]