# 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 <= 5000`
• `rollMax.length == 6`
• `1 <= rollMax[i] <= 15`

``````class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
int M = 1e9 + 7;
vector<vector<long>> dp(n + 1, vector<long>(6));
vector<long> sum(n + 1);
sum[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 6; ++j) {
for (int k = 1; k <= rollMax[j] && i >= k; ++k) {
dp[i][j] = (dp[i][j] + sum[i - k] - dp[i - k][j] + M) % M;
}
sum[i] = (sum[i] + dp[i][j]) % M;
}
}
return sum[n];
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1223

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

https://leetcode.com/problems/dice-roll-simulation/discuss/403756/Java-Share-my-DP-solution

https://leetcode.com/problems/dice-roll-simulation/discuss/423808/C%2B%2BJava-two-dimensional-DP-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation