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

这道题让模拟摇骰子的过程,每次随机摇出1到6之间的数字,但是给了一个限定条件,说是数字i不能连续摇出超过 rollMax[i-1] 次,现在让摇n次骰子,问可以摇出多少种不同的组合,结果对一个超大数取余。看到这种结果对一个超大数字取余的题,基本上可以直接放弃暴力破解的想法,直接无脑上动态规划 Dynamic Programming。现在来想一想,假如没有 rollMax 的限制条件,那么摇n次骰子可能出现组合总数就是6的n次方,现在有了这个限制条件,问题就变得复杂了,不然也对不起这 Hard 的身价。既然是要限定某个数字连续出现的次数不能超过一个限定值,则最后一次摇出的数字就是一个必备的信息,需要加到当前状态里,当然还需要知道当前是第几次摇,这样就需要两个变量来定义一个状态,于是用一个二维的 DP 数组,其中 dp[i][j] 表示摇了第i次且摇出的数字是 j+1 时的总的组合次数,于是所求的结果就是将所有的 dp[n][j] 加起来即可。

接下来的难点就是求状态转移方程了,对于任意一个状态 dp[i][j],不考虑限制条件的话,第i次摇出数字 j+1 的情况组合应该等于第 i-1 次摇出任意一个数字的情况总和,但是由于 rollMax[j] 第存在,不能使得数字 j+1 连续摇出 rollMax[j] 次,所以当前摇了第几次也很关键,可以另外用一个变量k从1遍历到i,这里当 k 小于 rollMax[j] 时,表示不受限制,可以连续摇出数字 j+1,但是这里我们不是直接加上上一轮所有的结果(为了方便知道每一轮的组合总数,用另一个数组 sum 来表示,其中 sum[i] 表示第i次摇的所有组合个数),而是要减去 dp[i-k][j],因为 dp[i-k][j] 中可能包括了当前不能加上的组合,比如当前数字 j+1 的限制次数是2次,而 dp[i-1][j] 里包括了 j+1 出现2次的情况,此时 dp[i][j] 直接加上这个会出现问题,所以要减去 dp[i-1][j] 的值,然后再去看 k=2 的情况,若超过次数限制了,就不加了,若没有,则还是同样的 logic,加上 sum[i-2],再减去 dp[i-2][j],最终到i等于k时,则 dp[i-k][j] 为0,而 sum[i-k] 是1,即可以将第一次摇出数字 j+1 的情况加上,不会漏掉任何一种情况,参见代码如下:

class Solution {
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        int M = 1e9 + 7;
        vector<vector<long>> dp(n + 1, vector<long>(6));
        vector<long> sum(n + 1);
        sum[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 6; ++j) {
                for (int k = 1; k <= rollMax[j] && i >= k; ++k) {
                    dp[i][j] = (dp[i][j] + sum[i - k] - dp[i - k][j] + M) % M;
                }
                sum[i] = (sum[i] + dp[i][j]) % M;
            }
        }
        return sum[n];
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1223

参考资料:

https://leetcode.com/problems/dice-roll-simulation/

https://leetcode.com/problems/dice-roll-simulation/discuss/403756/Java-Share-my-DP-solution

https://leetcode.com/problems/dice-roll-simulation/discuss/423808/C%2B%2BJava-two-dimensional-DP-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation