掷骰子模拟

标签: 数组 动态规划

难度: Hard

有一个骰子模拟器会每次投掷的时候生成一个 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

Submission

运行时间: 58 ms

内存: 17.4 MB

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        m = len(rollMax)  # 6
        f = [[0] * m for _ in range(n)]
        f[0] = [1] * m
        s = [0] * n
        s[0] = m
        for i in range(1, n):
            for j, mx in enumerate(rollMax):
                res = s[i - 1]
                if i > mx: res -= s[i - mx - 1] - f[i - mx - 1][j]
                elif i == mx: res -= 1
                f[i][j] = res % MOD
            s[i] = sum(f[i]) % MOD
        return s[-1]

# 作者：灵茶山艾府
# 链接：https://leetcode.cn/problems/dice-roll-simulation/solutions/2103292/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-sje6/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Explain

这个题解使用动态规划的方法来求解。定义 f[i][j] 为投掷了 i 次骰子，且第 i 次的结果为 j+1 的不同序列的数量。数组 s[i] 表示投掷 i 次骰子总共可能的不同序列数量。初始化第一次投掷的结果 f[0] = [1, 1, 1, 1, 1, 1]，因为第一次投掷每个数字都只有一种可能。对于每次投掷 i > 0，我们通过计算排除不符合 rollMax 限制的序列数量来更新 f[i][j]。如果投掷次数大于 j+1 可以连续出现的次数 mx，则需要减去那些不合法的序列。总结算后，s[i] 是所有 f[i][j] 的和，最终 s[n-1] 就是答案。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        m = 6  # 骰子的面数
        f = [[0] * m for _ in range(n)]  # 创建一个 n×m 的二维数组
        f[0] = [1] * m  # 初始化第一行，第一次投掷每个数字出现一次
        s = [0] * n  # 记录每次投掷的总序列数
        s[0] = m  # 第一次投掷总共有 m 种结果
        for i in range(1, n):
            for j, mx in enumerate(rollMax):
                res = s[i - 1]  # 前 i-1 次的序列总数
                if i > mx: res -= s[i - mx - 1] - f[i - mx - 1][j]  # 减去不合法的序列数
                elif i == mx: res -= 1  # 准确匹配到最大连续投掷限制，减去一种情况
                f[i][j] = res % MOD  # 取模保持计算规模
            s[i] = sum(f[i]) % MOD  # 计算当前所有可能的序列总数并取模
        return s[-1]  # 返回投掷 n 次的不同序列总数

Explore

在动态规划中，数组 f[i][j] 代表了在完成第 i 次投掷后，且第 i 次的结果为 j+1 的不同序列的数量。这个定义允许我们将问题分解为更小、更易管理的子问题。每个 f[i][j] 不仅记录了达到当前投掷结果的方式，而且保留了前 i 次投掷中，最后一个数字是 j+1 的所有可能序列的数量。这种方式使我们能够基于前一次的结果来更新当前次的结果，从而有效地利用动态规划解决问题。

当 i 大于 mx（骰子面 j+1 可以连续出现的最大次数）时，我们需要减去那些不合法的序列，即连续出现 j+1 超过 mx 次的序列。表达式 `s[i - mx - 1] - f[i - mx - 1][j]` 表示从前 i-mx-1 次投掷的总序列数中减去那些第 i-mx-1 次投掷结果为 j+1 的序列数。这样做是因为这些序列在接下来的 mx 次投掷中如果都选择 j+1，将导致超过了允许的最大连续次数，因此需要排除这部分不合法的序列。

当 `i == mx` 时，减去的 1 代表的是那个唯一的序列，其中所有的投掷结果都是 j+1，并且恰好连续出现了 mx 次。这是因为在达到 mx 次连续投掷时，唯一违反规则的序列就是所有投掷都选 j+1 的序列，因此我们只需要减去这一种情况。没有其他序列在这种投掷次数条件下违反了连续出现的最大次数限制。

在题解中使用 `s[i] = sum(f[i]) % MOD` 这一步是为了计算在完成第 i 次投掷后所有可能的不同序列总数。sum(f[i]) 是计算数组 f[i] 中所有元素的和，即将所有结束于不同骰子面的序列数量加在一起，从而得到总的序列数量。取模运算 MOD 是用来防止计算结果溢出，保持数值在一个可处理的范围内。这样，每次我们只关注有效的序列总数，确保计算的正确性和效率。