[LeetCode] 1223. Dice Roll Simulation

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)