Algorithm
Problem Name: 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. 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] <= 15
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
private final long MOD = (long) Math.pow(10, 9) + 7;
public int dieSimulator(int n, int[] rollMax) {
long[][] dp = new long[n][7];
for(int i = 0; i < 6; i++) {
dp[0][i] = 1;
}
dp[0][6] = 6;
for(int i = 1; i < n; i++) {
long sum = 0;
for(int j = 0; j < 6; j++) {
dp[i][j] = dp[i - 1][6];
if (i - rollMax[j] < 0) {
sum = (sum + dp[i][j]) % MOD;
} else {
if (i - rollMax[j] - 1 >= 0) {
dp[i][j] = (dp[i][j] - (dp[i - rollMax[j] - 1][6] - dp[i - rollMax[j] - 1][j])) % MOD + MOD;
} else {
dp[i][j] = (dp[i][j] - 1) % MOD;
}
sum = (sum + dp[i][j]) % MOD;
}
}
dp[i][6] = sum;
}
return (int) (dp[n - 1][6]);
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const dieSimulator = function(n, rollMax) {
const mod = 10 ** 9 + 7
const faces = rollMax.length
const dp = Array.from({ length: n + 1 }, () => new Array(faces + 1).fill(0))
dp[0][faces] = 1
for(let j = 0; j < faces; j++) {
dp[1][j] = 1
}
dp[1][faces] = faces
for(let i = 2; i < n + 1; i++) {
for(let j = 0; j < faces; j++) {
for(let k = 1; k < rollMax[j] + 1; k++) {
if(i - k < 0) break
dp[i][j] += dp[i - k][faces] - dp[i - k][j]
dp[i][j] %= mod
}
}
dp[i][faces] = dp[i].reduce((ac, e> => ac + e, 0)
}
return dp[n][faces] % mod
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def dieSimulator(self, n: int, r: List[int]) -> int:
K = max(r)
dp = [[[0 for k in range(K)] for j in range(6)] for i in range(n)]
for j in range(6): dp[0][j][0] = 1
for i in range(1, n):
for j in range(6):
dp[i][j][0] += sum(dp[i-1][t][k] for t in range(6) for k in range(r[t]) if t != j)
for k in range(1, r[j]):
dp[i][j][k] = dp[i-1][j][k-1]
return sum(dp[n-1][j][k] for j in range(6) for k in range(K)) % (10**9+7)
Input
Output