Formatted question description: https://leetcode.ca/all/1223.html

# 1223. Dice Roll Simulation (Medium)

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

Related Topics:
Dynamic Programming

## Solution 1. DP

Let dp[i][j] be the number of distinct sequences ending with j obtained using i rolles.

dp[j] = 1       1 <= j <= 6


Ignoring the rollMax, we have dp[i][j] = sum( dp[i-1][k] | 1 <= k <= 6 ).

If we pick j at i roll, we need to exclude the cases where there are already rollMax[j] j numbers right in front of ith roll.

The number of such cases is dp[i-rollMax[j]-1][k] where 1 <= k <= 6 and k != j.

// OJ: https://leetcode.com/problems/dice-roll-simulation/

// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/dice-roll-simulation/discuss/403756/Java-Share-my-DP-solution
class Solution {
public:
int dieSimulator(int n, vector<int>& A) {
long mod = 1e9+7;
vector<vector<long>> dp(n, vector<long>(7));
for (int i = 0; i < 6; ++i) dp[i] = 1;
dp = 6;
for (int i = 1; i < n; ++i) {
long sum = 0;
for (int j = 0; j < 6; ++j) {
dp[i][j] = dp[i - 1];
if (i < A[j]) sum = (sum + dp[i][j]) % mod;
else {
if (i - A[j] - 1 >= 0) dp[i][j] = (dp[i][j] - (dp[i - A[j] - 1] - dp[i - A[j] - 1][j]) + mod) % mod;
else dp[i][j] = (dp[i][j] - 1) % mod;
sum = (sum + dp[i][j]) % mod;
}
}
dp[i] = sum;
}
return dp[n - 1];
}
};


Java

class Solution {
public int dieSimulator(int n, int[] rollMax) {
final int MODULO = 1000000007;
int[][][] dp = new int[n];
for (int i = 0; i < 6; i++)
dp[i] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 6; j++) {
for (int k = 0; k < 6; k++) {
if (k == j)
continue;
for (int m = 0; m < 15; m++)
dp[i][j] = (dp[i][j] + dp[i - 1][k][m]) % MODULO;
}
int max = rollMax[j];
for (int k = 1; k < max; k++)
dp[i][j][k] = dp[i - 1][j][k - 1];
}
}
int sum = 0;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 15; j++)
sum = (sum + dp[n - 1][i][j]) % MODULO;
}
return sum;
}
}