[leetcode] 1223. Dice Roll Simulation

[leetcode] 1223. Dice Roll Simulation

Description

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.

Two sequences are considered different if at least one element differs from each other. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 2, rollMax = [1,1,2,2,2,3]Output: 34Explanation: 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

分析

题目的意思是：这道题的意思是置n次骰子，骰子有6个点数，其中rollMax规定每个点最多连续置出的点数。这道题最直接的方式是dp，但是比较麻烦，因为加了一个连续置出的点数的限制，思路我参考了一下别人的。

dp[i][j][k] 表示 长度为i，以k个j结尾的骰子序列，一共有多少种. 0 <= i

for p in range(6): if p != j: f[i][j][k] += (sum(f[i-1][p]) % MOD)

如果以k个j结尾（k > 1）：

f[i][j][k] = f[i-1][j][k-1]

最终的结果是sum(dp[n-1]),因为是三位数组，所以求和是双层循环。

这道题很难想到，我把解答过程记录下来慢慢欣赏

代码

class Solution: def dieSimulator(self, n: int, rollMax: List[int]) -> int: MOD=10**9+7 dp=[[[0]*(max(rollMax)+1) for i in range(6)] for j in range(n)] for i in range(6): dp[0][i][1]=1 # 第1次掷骰子，点数为i且连续一次 for i in range(1,n): # 第i次掷骰子，0-start for j in range(6): # 第i次掷出j点，j=0~5表示1-6点 for k in range(1,rollMax[j]+1): if(k==1): for p in range(6): if(p!=j): dp[i][j][k]+=sum(dp[i-1][p])%MOD else: dp[i][j][k]=dp[i-1][j][k-1] res=0 for j in range(6): for k in range(1,rollMax[j]+1): res=(res+dp[n-1][j][k])%MOD return res

参考文献

​​花花酱 LeetCode 1223. Dice Roll Simulation​​​​Python3 动态规划​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。