# 1223. Dice Roll Simulation

A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] (1-indexed) consecutive times.

Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls.

Two sequences are considered different if at least one element differs from each other. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 2, rollMax = [1,1,2,2,2,3]
Output: 34
Explanation: There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.

Example 2:

Input: n = 2, rollMax = [1,1,1,1,1,1]
Output: 30

Example 3:

Input: n = 3, rollMax = [1,1,1,2,2,3]
Output: 181

# Solution

Approach 1: DP (backtracking gets TLE).

# Code (Python)

Approach 1:

class Solution:
    def dieSimulator1(self, n: int, roll_max: List[int]) -> int:
        # DP. https://leetcode.com/problems/dice-roll-simulation/discuss/404840/Short-Python-DP-with-detailed-image-explanation
        #count[i][j]: roll n times where the last face value is j (0-5)
        # 1 consecutive 5 -- xxxy5 where y!=5 : sum(count[i-1]) - count[i-2][j]
        # count[i][j] = (sum(count[i-1]) - count[i-1][j]) + (sum(count[i-2]) - count[i-2][j]) + ... (for roll_max[j] times)
        count = [[0] * (len(roll_max) + 1) for _ in range(n + 1)]
        count[0][-1] = 1
        count[1] = [1] * len(roll_max) + [len(roll_max)]
        
        for i in range(2, n + 1):
            for j in range(len(roll_max)):
                for m in range(1, roll_max[j] + 1):
                    if i - m < 0:
                        break
                    count[i][j] += count[i-m][-1] - count[i-m][j]
            count[i][len(roll_max)] = sum(count[i])
        
        return int(count[-1][-1] % (10 ** 9 + 7))

# Code (C++)

Approach 1:

Approach 2: