1223. Dice Roll Simulation


题目

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 <= 5000
  • rollMax.length == 6
  • 1 <= 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点赞!


发表回复

您的电子邮箱地址不会被公开。