# 1223. Dice Roll Simulation

Contents

## 题目

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`

## 解法1

dp[n]肯定没戏，我们不知道dp[n]的结尾是啥数字，由dp[n]没办法往后推。

``````class Solution(object):
def dieSimulator(self, n, rollMax):
"""
:type n: int
:type rollMax: List[int]
:rtype: int
"""
_m = {}
def _dp(i, j, k):
if (i, j, k) in _m:
return _m[(i, j, k)]
if k > i or i <= 0:
return 0
elif k == i:
return 1
ret = 0
for j_ in range(6):
if j_ == j:
continue
for k_ in range(1, rollMax[j_] + 1):
ret += _dp(i - k, j_, k_)
ret = ret % (10 ** 9 + 7)
_m[(i, j, k)] = ret
return ret

ans = 0
for j in range(6):
for k in range(1, rollMax[j] + 1):
ans += _dp(n, j, k)

return ans % (10 ** 9 + 7)``````

``RecursionError: maximum recursion depth exceeded in comparison``

``````class Solution(object):
def dieSimulator(self, n, rollMax):
"""
:type n: int
:type rollMax: List[int]
:rtype: int
"""
_dp = [[[0] * (max(rollMax) + 1) for _ in range(6)] for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(6):
for k in range(1, rollMax[j] + 1):
if k > i or i < 0:
_dp[i][j][k] = 0
elif k == i:
_dp[i][j][k] = 1
else:
val = 0
for j_ in range(6):
if j_ == j:
continue
for k_ in range(1, rollMax[j_] + 1):
if i - k < 0:
continue
val += _dp[i - k][j_][k_]
val = val % (10 ** 9 + 7)
_dp[i][j][k] = val

ans = 0
for j in range(6):
for k in range(1, rollMax[j] + 1):
ans += _dp[n][j][k]

return ans % (10 ** 9 + 7)``````

## 解法2（标准解法）

dp[i][j]代表前i位在以j结尾时的枚举数量，sum[i]代表前i位的合法组合数量。

``````class Solution(object):
def dieSimulator(self, n, rollMax):
"""
:type n: int
:type rollMax: List[int]
:rtype: int
"""
dp = [[0] * 6 for _ in range(n + 1)]
sums = [0] * (n + 1)
sums[0] = 1
for i in range(1, n + 1):
for j in range(6):
for k in range(1, min(i, rollMax[j]) + 1):
dp[i][j] += sums[i - k] - dp[i - k][j]
sums[i] += dp[i][j]

return sums[n] % (10 ** 9 + 7)``````

——此处是内容的分割线——