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.
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);
}
};