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


Constraints:

• 1 <= n <= 5000
• rollMax.length == 6
• 1 <= rollMax[i] <= 15

Solutions: DP

Naive one:

def: dp[i][j][k] := # of sequences ends with k consecutive j after i rolls
Init: dp[1][*][1] = 1

transition:
dp[i][j][1] = sum(dp[i-1][p][*]), p != j
dp[i][j][k + 1] = dp[i-1][j]][k]

Time complexity: O(n*6*6*15)
Space complexity: O(n*6*15) -> O(6*15)

Solution 2: DP with compressed state

dp[i][j] := # of sequences of length i end with j
dp[i][j] := sum(dp[i-1]) – invalid

Time complexity: O(n*6)
Space complexity: O(n*6)

C++

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode