The Dice Roll Simulation problem asks you to determine how many different sequences of dice rolls are possible, given certain constraints. Specifically:
n representing the total number of dice rolls.rollMax of length 6, where rollMax[i] is the maximum number of times that face i+1 can appear consecutively in a sequence.
Your task is to count the number of possible sequences of length n such that no face appears more than its allowed consecutive times. The answer should be returned modulo 10^9 + 7.
Key constraints:
rollMax.n (up to 5000), so efficiency matters.
At first glance, you might think to generate all possible dice roll sequences of length n and count the valid ones. However, this would be extremely slow due to the exponential number of possibilities (6n).
The main challenge is to efficiently ensure that no face appears more than its allowed consecutive times. This suggests keeping track of:
We use dynamic programming to solve this problem efficiently. The main idea is to define a DP state that captures all necessary information to make decisions:
dp[roll][last][count] represents the number of valid sequences of length roll, ending with face last (0-based), where last has appeared count times consecutively at the end.count < rollMax[last]. If it is a different face, we reset the consecutive count to 1.dp[n][last][count] for all faces and all valid counts.
To optimize space, we can use two DP arrays (current and previous) or a 3D DP array of size n x 6 x max(rollMax).
This approach ensures we never compute the same subproblem twice and always respect the constraints on consecutive rolls.
Let's consider n = 3 and rollMax = [1,1,1,2,2,3].
The DP tracks, for each step, which faces are allowed and how many times they have appeared consecutively. By the end, we sum all valid sequences of length 3.
Brute-force approach: Would be O(6n), since every roll has 6 choices, which is infeasible for large n.
DP approach:
n rolls, 6 possible last faces, and up to max(rollMax) consecutive counts.n * 6 * max(rollMax)).n * 6 * max(rollMax) * 6), but since max(rollMax) is at most 15, this is efficient.n * 6 * max(rollMax)), but can be reduced to O(6 * max(rollMax)) by reusing arrays.The Dice Roll Simulation problem is a classic example where dynamic programming shines. By carefully defining a state that tracks the number of rolls, the last face, and its consecutive count, we efficiently count all valid sequences. The approach avoids repeated work and respects all constraints, making it both elegant and practical for large inputs.
MOD = 10 ** 9 + 7
class Solution:
def dieSimulator(self, n: int, rollMax: List[int]) -> int:
dp = [[[0] * 16 for _ in range(6)] for _ in range(n + 1)]
for i in range(6):
dp[1][i][1] = 1
for roll in range(2, n + 1):
for last in range(6):
for count in range(1, rollMax[last] + 1):
if dp[roll - 1][last][count]:
for nxt in range(6):
if nxt == last:
if count + 1 <= rollMax[last]:
dp[roll][last][count + 1] = (dp[roll][last][count + 1] + dp[roll - 1][last][count]) % MOD
else:
dp[roll][nxt][1] = (dp[roll][nxt][1] + dp[roll - 1][last][count]) % MOD
res = 0
for last in range(6):
for count in range(1, rollMax[last] + 1):
res = (res + dp[n][last][count]) % MOD
return res
class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
const int MOD = 1e9 + 7;
int dp[n + 1][6][16] = {};
for (int i = 0; i < 6; ++i)
dp[1][i][1] = 1;
for (int roll = 2; roll <= n; ++roll) {
for (int last = 0; last < 6; ++last) {
for (int count = 1; count <= rollMax[last]; ++count) {
if (dp[roll - 1][last][count]) {
for (int nxt = 0; nxt < 6; ++nxt) {
if (nxt == last) {
if (count + 1 <= rollMax[last])
dp[roll][last][count + 1] = (dp[roll][last][count + 1] + dp[roll - 1][last][count]) % MOD;
} else {
dp[roll][nxt][1] = (dp[roll][nxt][1] + dp[roll - 1][last][count]) % MOD;
}
}
}
}
}
}
int res = 0;
for (int last = 0; last < 6; ++last)
for (int count = 1; count <= rollMax[last]; ++count)
res = (res + dp[n][last][count]) % MOD;
return res;
}
};
class Solution {
public int dieSimulator(int n, int[] rollMax) {
int MOD = 1000000007;
int[][][] dp = new int[n + 1][6][16];
for (int i = 0; i < 6; ++i)
dp[1][i][1] = 1;
for (int roll = 2; roll <= n; ++roll) {
for (int last = 0; last < 6; ++last) {
for (int count = 1; count <= rollMax[last]; ++count) {
if (dp[roll - 1][last][count] > 0) {
for (int nxt = 0; nxt < 6; ++nxt) {
if (nxt == last) {
if (count + 1 <= rollMax[last])
dp[roll][last][count + 1] = (dp[roll][last][count + 1] + dp[roll - 1][last][count]) % MOD;
} else {
dp[roll][nxt][1] = (dp[roll][nxt][1] + dp[roll - 1][last][count]) % MOD;
}
}
}
}
}
}
int res = 0;
for (int last = 0; last < 6; ++last)
for (int count = 1; count <= rollMax[last]; ++count)
res = (res + dp[n][last][count]) % MOD;
return res;
}
}
var dieSimulator = function(n, rollMax) {
const MOD = 1e9 + 7;
let dp = Array.from({length: n + 1}, () =>
Array.from({length: 6}, () => Array(16).fill(0))
);
for (let i = 0; i < 6; ++i) dp[1][i][1] = 1;
for (let roll = 2; roll <= n; ++roll) {
for (let last = 0; last < 6; ++last) {
for (let count = 1; count <= rollMax[last]; ++count) {
if (dp[roll - 1][last][count]) {
for (let nxt = 0; nxt < 6; ++nxt) {
if (nxt === last) {
if (count + 1 <= rollMax[last])
dp[roll][last][count + 1] = (dp[roll][last][count + 1] + dp[roll - 1][last][count]) % MOD;
} else {
dp[roll][nxt][1] = (dp[roll][nxt][1] + dp[roll - 1][last][count]) % MOD;
}
}
}
}
}
}
let res = 0;
for (let last = 0; last < 6; ++last)
for (let count = 1; count <= rollMax[last]; ++count)
res = (res + dp[n][last][count]) % MOD;
return res;
};