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 <= 5000rollMax.length == 61 <= rollMax[i] <= 15
思路
题目大意是，在给定每面数最大连续次数的前提下，求掷骰子的组合数。
排列组合问题+刷题第一定律（10e9+7，无脑动规），dp是没得跑了。
下面开始想状态表示和转移方程。
解法1
首先想想状态表示，我们需要找一个可重入的可递推的状态表示。
dp[n]肯定没戏，我们不知道dp[n]的结尾是啥数字，由dp[n]没办法往后推。
一维不行，我们就加状态，这里我给出的是dp[i][j][k]，代表前i位，在最后连续k个数字为j时的组合数量。
这样定义超级简单，递推关系不用多说了吧。在已知末尾有k个j的情况下，前面不能再有j了，把其他数字的重复情况枚举下就可以了。
美中不足是时间复杂度可能大了点：（
时间复杂度O(n * sum(rollMax) * sum(rollMax))
版本1（TLE）
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)
提交上去，毫无悬念的TLE了，本地研究下吧。
本地跑下这组测试样例，报错栈溢出。
RecursionError: maximum recursion depth exceeded in comparison这个好办，修改下最大栈深度，2.32s，属于可过可不过的性能。
状态基本是稠密的，且dp[i]只与dp[i]之前的状态有关，可以改成循环。
去掉递归，改成循环试试。
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)本地耗时1.42s。
提交上去，贴地过。
解法2（标准解法）
让我们再来看看最优解法
dp[i][j]代表前i位在以j结尾时的枚举数量，sum[i]代表前i位的合法组合数量。
难点在于递推关系。
考虑dp[i][j]，即长度为i的串，以j结尾时，结尾处的j可以重复1,2,…rollMax个，故这种case对dp[i][j]的贡献为sum[i – k] – dp[i – k][j]。——sum[i – k]为长度i-k的组合数量，为什么这里要减去dp[i – k][j]呢？因为计算长度为k的重复j时，串i-k的结尾不能再为j，否则会有重复计算。
枚举k，累加到dp[i][j]即可。
时间复杂度O(n * sum(rollMax))
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)搞定，收工！
——此处是内容的分割线——
除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接
本文链接：https://www.utopiafar.com/2022/06/16/leetcode-1223-dice-roll-simulation/
码字不易，如果觉得内容有帮助，欢迎留言or点赞！