What is the main pattern to solve Dice Roll Simulation?

The main pattern is state transition dynamic programming, where each DP state tracks the last number rolled and its consecutive count.

How do I handle large n in Dice Roll Simulation?

Use modulo 10^9 + 7 at each DP accumulation to manage large numbers and prevent integer overflow efficiently.

Can sequences with different consecutive numbers be merged in DP?

No, each sequence state must track the last number and its consecutive count separately to respect rollMax constraints.

Is it necessary to initialize DP for all numbers at position 0?

Yes, each number can start a valid sequence, so initialize dp[0][i][1] = 1 for all numbers 1 through 6.

How does GhostInterview avoid common pitfalls in this problem?

It helps by highlighting invalid consecutive counts, enforcing rollMax limits, and checking modular arithmetic throughout the DP table.

#1223

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

掷骰子模拟

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。不过我们在使用它时有个约束，就是使得投掷骰子时，连续掷出数字 i 的次数不能超过 rollMax[i] （ i 从 1 开始编号）。现在，给你一个整数数组 rollMax 和一个整数 n ，请你来计算掷 n 次骰子可得到的不同点…

数组动态规划

题目描述

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。

不过我们在使用它时有个约束，就是使得投掷骰子时，连续掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。

现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。

假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。

示例 1：

输入：n = 2, rollMax = [1,1,2,2,2,3]
输出：34
解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 = 34。

示例 2：

输入：n = 2, rollMax = [1,1,1,1,1,1]
输出：30

示例 3：

输入：n = 3, rollMax = [1,1,1,2,2,3]
输出：181

提示：

1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

lightbulb

解题思路

方法一：记忆化搜索

我们可以设计一个函数 $dfs(i, j, x)$ 表示从第 $i$ 次掷骰子开始，当前掷出的点数为 $j$ ，且连续掷出 $j$ 的次数为 $x$ 的方案数。其中 $j$ 的取值范围为 $[1, 6]$ ，而 $x$ 的取值范围为 $[1, rollMax[j - 1]]$ 。那么答案就是 $dfs(0, 0, 0)$ 。

函数 $dfs(i, j, x)$ 的计算过程如下：

如果 $i \ge n$ ，说明已经掷完了 $n$ 次骰子，返回 $1$ 。
否则，我们枚举下一次掷出的点数 $k$ ，如果 $k \ne j$ ，那么我们可以直接掷出 $k$ ，此时连续掷出 $j$ 的次数 $x$ 就会被重置为 $1$ ，因此方案数为 $dfs(i + 1, k, 1)$ 。如果 $k = j$ ，那么我们需要判断 $x$ 是否小于 $rollMax[j - 1]$ ，如果小于，那么我们可以继续掷出 $j$ ，此时连续掷出 $j$ 的次数 $x$ 就会加 $1$ ，因此方案数为 $dfs(i + 1, j, x + 1)$ 。最后将所有方案数相加，即为 $dfs(i, j, x)$ 的值。注意答案可能很大，因此需要对 $10^9 + 7$ 取模。

过程中，我们可以使用记忆化搜索避免重复计算。

时间复杂度 $O(n \times k^2 \times M)$ ，空间复杂度 $O(n \times k \times M)$ 。其中 $k$ 为点数的取值范围，而 $M$ 为连续掷出某个点数的最大次数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @cache
        def dfs(i, j, x):
            if i >= n:
                return 1
            ans = 0
            for k in range(1, 7):
                if k != j:
                    ans += dfs(i + 1, k, 1)
                elif x < rollMax[j - 1]:
                    ans += dfs(i + 1, j, x + 1)
            return ans % (10**9 + 7)

        return dfs(0, 0, 0)

speed

复杂度分析

指标	值
时间	complexity depends on n, the number of dice rolls, and the maximum rollMax values because the DP array tracks positions, last numbers, and consecutive counts. Space complexity also scales with n * 6 * max(rollMax) for storing intermediate DP states.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if you are tracking consecutive rolls correctly and respecting rollMax limits.
question_mark
Consider how to reduce unnecessary iterations by limiting counts according to rollMax.
question_mark
Think about modular arithmetic to prevent integer overflow for large n.

warning

常见陷阱

外企场景

error
Not resetting consecutive count when the next roll differs from the last number.
error
Exceeding rollMax for a number by miscounting consecutive occurrences.
error
Forgetting to apply modulo 10^9 + 7 after each DP accumulation step.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Dice sequences with varying die faces, not fixed at 6, with per-face rollMax constraints.
arrow_right_alt
Count sequences where only specific numbers have consecutive roll limits, while others are unrestricted.
arrow_right_alt
Compute sequences where the order matters, but consecutive repetitions are allowed up to different rollMax thresholds for subsets of numbers.

help

常见问题

外企场景

继续练习

#1218 最长定差子序列 #1235 规划兼职工作 #1191 K 次串联后最大子数组之和