# 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: