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. Since the answer may be too large, return it modulo 109 + 7.
Two sequences are considered different if at least one element differs from each other.
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 <= 5000rollMax.length == 61 <= rollMax[i] <= 15Problem Overview: You roll a 6-sided dice n times, but each face has a limit on how many times it can appear consecutively. The array rollMax[6] defines that limit for each face. The goal is to count how many valid sequences of length n exist without violating those consecutive constraints.
Approach 1: Dynamic Programming with 3D Array (Time: O(n * 6 * maxRoll), Space: O(n * 6 * maxRoll))
This approach tracks three pieces of state: the roll index, the face value, and the current streak length of that face. Define dp[i][j][k] as the number of ways to reach roll i where the last face is j and it has appeared k consecutive times. For every new roll, iterate over all previous faces. If the same face appears again, increase the streak only if k + 1 ≤ rollMax[j]. If a different face appears, reset the streak to 1. This explicitly models every valid state and ensures constraints are respected at each step. It’s straightforward to implement and useful for understanding state transitions in dynamic programming.
Approach 2: Dynamic Programming with 2D Array (Time: O(n * 6), Space: O(n * 6))
The 3D state can be compressed by tracking only the total sequences ending with each face. Let dp[i][j] represent the number of sequences of length i ending with face j. Normally you would extend from the total sequences of length i-1, but you must subtract sequences that would violate the rollMax constraint. When the streak of face j would exceed its limit, remove those invalid contributions using previously computed states. This converts the explicit streak dimension into arithmetic on previous totals. The result is significantly fewer states while still enforcing the constraints.
This optimization is common in dynamic programming problems where a dimension can be inferred from earlier values. The dice faces themselves are stored in a simple array, and transitions iterate over the six possible outcomes each step.
Recommended for interviews: Start by describing the 3D DP state because it clearly models the constraints and shows you understand the problem structure. Then mention the 2D optimization that removes the streak dimension. Interviewers typically expect the optimized dynamic programming approach since it reduces memory and keeps the time complexity near linear in n.
In this approach, we'll use a 3D dynamic programming (DP) array to keep track of the number of ways to have a valid sequence up to the ith roll, ending with j as the last rolled number, with k consecutive rolls of j.
Our main DP state can be expressed as dp[i][j][k], where i represents the number of rolls, j represents the last face value, and k represents how many times this face value has been rolled consecutively.
For the transition, notice that if we want the current roll to be number j, we can extend a sequence ending with j k times using the face j again if k < rollMax[j-1]. If we use a different number instead, we reset k to 1 for a new number.
This Python solution uses a 3D DP array to keep track of valid rolls, as discussed. The final result is computed by summing up all valid sequences of length n for any face and consecutive counts allowed by rollMax.
Python
JavaScript
Time Complexity: O(n * 6 * 6 * m) where m = max(rollMax)
Space Complexity: O(n * 6 * m)
Instead of a 3D array, this approach uses a 2D array, where dp[i][j] represents the number of sequences of length i that end with number j, without specifically tracking consecutive count. This approach is less memory intensive but requires careful bookkeeping of the last rolled sequences according to constraints.
This Java solution employs a 2D DP array to find valid sequences. With each roll, it updates the sum of possibilities by calculating across different faces.
Time Complexity: O(n * 6 * 6)
Space Complexity: O(n * 6)
We can design a function dfs(i, j, x) to represent the number of schemes starting from the i-th dice roll, with the current dice roll being j, and the number of consecutive times j is rolled being x. The range of j is [1, 6], and the range of x is [1, rollMax[j - 1]]. The answer is dfs(0, 0, 0).
The calculation process of the function dfs(i, j, x) is as follows:
i \ge n, it means that n dice have been rolled, return 1.k rolled next time. If k \ne j, we can directly roll k, and the number of consecutive times j is rolled will be reset to 1, so the number of schemes is dfs(i + 1, k, 1). If k = j, we need to judge whether x is less than rollMax[j - 1]. If it is less, we can continue to roll j, and the number of consecutive times j is rolled will increase by 1, so the number of schemes is dfs(i + 1, j, x + 1). Finally, add all the scheme numbers to get the value of dfs(i, j, x). Note that the answer may be very large, so we need to take the modulus of 10^9 + 7.During the process, we can use memoization search to avoid repeated calculations.
The time complexity is O(n times k^2 times M), and the space complexity is O(n times k times M). Here, k is the range of dice points, and M is the maximum number of times a certain point can be rolled consecutively.
We can change the memoization search in Solution 1 to dynamic programming.
Define f[i][j][x] as the number of schemes for the first i dice rolls, with the i-th dice roll being j, and the number of consecutive times j is rolled being x. Initially, f[1][j][1] = 1, where 1 leq j leq 6. The answer is:
$
sum_{j=1}^6 sum_{x=1}^{rollMax[j-1]} f[n][j][x]
We enumerate the last dice roll as j, and the number of consecutive times j is rolled as x. The current dice roll can be 1, 2, cdots, 6. If the current dice roll is k, there are two cases:
, we can directly roll k, and the number of consecutive times j is rolled will be reset to 1. Therefore, the number of schemes f[i][k][1] will increase by f[i-1][j][x]., we need to judge whether x+1 is less than or equal to rollMax[j-1]. If it is less than or equal to, we can continue to roll j, and the number of consecutive times j is rolled will increase by 1. Therefore, the number of schemes f[i][j][x+1] will increase by f[i-1][j][x].The final answer is the sum of all f[n][j][x].
The time complexity is O(n times k^2 times M), and the space complexity is O(n times k times M). Here, k is the range of dice points, and M$ is the maximum number of times a certain point can be rolled consecutively.
| Approach | Complexity |
|---|---|
| Dynamic Programming with 3D Array | Time Complexity: O(n * 6 * 6 * m) where m = max(rollMax) |
| Dynamic Programming with 2D Array | Time Complexity: O(n * 6 * 6) |
| Memoization Search | — |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with 3D Array | O(n * 6 * maxRoll) | O(n * 6 * maxRoll) | Best for understanding the full DP state including roll index, face, and streak length |
| Dynamic Programming with 2D Array | O(n * 6) | O(n * 6) | Preferred optimized solution when reducing state dimensions for better performance |
LeetCode 1223. Dice Roll Simulation • Happy Coding • 5,004 views views
Watch 9 more video solutions →Practice Dice Roll Simulation with our built-in code editor and test cases.
Practice on FleetCode