1223. Dice Roll Simulation

2019年10月13号，LeetCode contest question3

problem 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: 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

algorithm thought

第三次参加比赛了，当时又止步在第三题。第三题当时其实想到用记忆化保存的方法解决问题，但是最后没有想通状态转移的过程。于是之后参考了discuss里大神的逻辑，然后自己写出代码

类似一个安放数字问题，也很像回溯法构建一个排列的问题。只是回溯法需要列举出所有的情况，但是这里只需要返回最后的数字。所以就可以不用回溯的过程。这里需要多考虑的一点是，存在一个限制数组，rollMax。这里就需要记录当前数字之前出现了多少次，如果超过了限制，那么这次安放就不安放这个数字。这里的算法中，会出现很多重复计算的过程，很多前面的数字最后会汇聚到一个节点，如果不用记忆化方法保存之前的数据，肯定会Time Limit Error。所以这里用数组保存之前的结果。整个动态规划的状态有3个维度，一是前面出现的次数，二是前一个数字，三是当前防止的轮数。

所以，所有的结果可以看成是下面6项相加

f(1,1,1),f(1,2,1),f(1,3,1),f(1,4,1),f(1,5,1),f(1,6,1).

code

class Solution {
public:
    long long cache[5002][7][16];
    long long mod=1000000000+7;
    vector<int> rollMax;
    int dieSimulator(int n, vector<int>& rollMax) {
        memset(cache,-1,sizeof(cache));
        this->rollMax=rollMax;
        return dp(0,0,0,n);
    }
    long long dp(int per,int number,int pos,int n){
        if(pos==n)
            return 1;
        if(cache[pos][number][per]!=-1)
            return cache[pos][number][per];
        long long res=0;
        for(int i=1;i<=6;++i){
            if(i==number){
                if(per+1<=rollMax[i-1])
                    res+=dp(per+1,i,pos+1,n);
            }else{
                res+=dp(1,i,pos+1,n);
            }
        }
        return cache[pos][number][per]=(res%mod);
    }
};

algorithm analysis

如果不加记忆模式，时间复杂度就跟回溯法是一样的，但是加了记忆模式，算法快了很多，时间复杂度这里不好分析