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
Solution:
class Solution {
int mod = (int) 1e9 + 7;
Integer[][][] dp;
public int dieSimulator(int n, int[] rollMax) {
dp = new Integer[n][6][16];
int res = helper(0, n, -1, 0, rollMax);
return res;
}
private int helper(int i, int n, int last, int count, int[] rollMax) {
if (i == n) return 1;
if (last != -1 && dp[i][last][count] != null) return dp[i][last][count];
int res = 0;
for (int v = 0; v < 6; v ++) {
if (v == last && count < rollMax[last]) {
res = (res + helper(i + 1, n, last, count + 1, rollMax)) % mod;
}
if (v != last) {
res = (res + helper(i + 1, n, v, 1, rollMax)) % mod;
}
}
if (last != -1) return dp[i][last][count] = res;
return res;
}
}