本文共 4189 字，大约阅读时间需要 13 分钟。

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

解题思路

这题使用dfs加cache可以过。具体思路如下：

考虑每个位置需要摆放的数i（其中0<=i<6），判断i和之前元素pre是不是一样，如果一样并且i的连续个数等于rollMax[i]，此时i就不能放入当前位置，那么可以将i+1放入当前位置，依次递归下去将所有的数放好即可。接着思考边界条件，也非常简单，就是当当我们遍历完全部的n个数就（表示当前位置上的数都放好了）此时返回1（表示这是一个可行解）。

from functools import lru_cacheclass Solution:    def dieSimulator(self, n: int, rollMax: List[int]) -> int:        @lru_cache(None)        def dfs(n, pre, k):            if n == 0:                return 1            res = 0            for i in range(6):                if i == pre and k == rollMax[i]:                    continue                res = (res + dfs(n - 1, i, k + 1 if i == pre else 1))%(10**9 + 7)            return res        return dfs(n, -1, 0)

由于使用了lru_cache所以代码非常简洁。当然可以使用dfs加记忆化的问题也可以使用动态规划来做。定义函数$f(i,j,k)$表示第$i$掷次骰子，并且数字$j$在之前出现了$k$次的总次数。那么

• $f(i,j,0)={\sum }_{t=0}^{6}f(i-1,t,k)ift\ne j$
• $f(i,j,k)=f(i-1,t,k-1)ift=j$

class Solution:    def dieSimulator(self, n: int, rollMax: List[int]) -> int:        Max, mod = max(rollMax), 10**9 + 7        dp = [[[0]*Max for _ in range(6)] for _ in range(n)]         for i in range(6):             dp[0][i][0] = 1        for i in range(1, n):            for j in range(6):                dp[i][j][0] = sum(dp[i-1][t][k] for t in range(6) for k in range(rollMax[t]) if t != j)%mod                for k in range(rollMax[j]-1, 0, -1):                    dp[i][j][k] = dp[i-1][j][k-1]        return sum(dp[n-1][j][k] for j in range(6) for k in range(Max)) % mod

上述代码可以继续优化。我们可以先计算和，在通过和减去j==t的情况。

• $f(i,j,0)={\sum }_{t=0}^{6}f(i-1,t,k)-f(i-1,j,k)$

这种做法效率比上面更高。

class Solution:    def dieSimulator(self, n: int, rollMax: List[int]) -> int:        Max, mod = max(rollMax), 10**9 + 7        dp = [[[0]*Max for _ in range(6)] for _ in range(n)]         for i in range(6):             dp[0][i][0] = 1        for i in range(1, n):            tmp = [sum(row) for row in dp[i-1]]            Sum = sum(tmp)            for j in range(6):                dp[i][j][0] = Sum - tmp[j]                 for k in range(rollMax[j]-1, 0, -1):                    dp[i][j][k] = dp[i-1][j][k-1]        return sum(dp[n-1][j][k] for j in range(6) for k in range(Max)) % mod

我们实际上不用开辟三维数组，只用二维数组即可，具体操作如下：

class Solution:    def dieSimulator(self, n: int, rollMax: List[int]) -> int:        Max, mod = max(rollMax), 10**9 + 7        dp = [[0, 1] + [0]*(Max - 1) for i in range(6)]        for i in range(1, n):            tmp = [sum(row[1:]) for row in dp]            Sum = sum(tmp)            for j in range(6):                dp[j][0] = (Sum - tmp[j]) % mod                for k in range(rollMax[j], 0, -1):                    dp[j][k] = dp[j][k - 1]        return sum(sum(row[1:]) for row in dp) % mod

你以为这就是全部，实际上上面的代码还可以继续优化。我们在代码中使用了大量的sum函数，实际上这些都可以嵌入到循环中，具体操作如下：

class Solution:    def dieSimulator(self, n: int, rollMax: List[int]) -> int:        Max, mod = max(rollMax), 10**9 + 7        dp = [[0, 1] + [0]*(Max - 1) for i in range(6)]        tmp, Sum = [1] * 6, 6        for i in range(1, n):            ts = 0            for j in range(6):                dp[j][0], tmp[j] = (Sum - tmp[j]) % mod, 0                for k in range(rollMax[j], 0, -1):                    dp[j][k] = dp[j][k - 1]                    tmp[j] += dp[j][k]                ts += tmp[j]            Sum = ts % mod        return Sum

至此这个问题才告一段落，我已开始在解这个问题的时候一直在寻找数学解法，但是没有思考出来，这一部分有待更新。

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/102546598 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！