有一个骰子模拟器会每次投掷的时候生成一个
1到6的随机数。
不过我们在使用它时有个约束，就是使得投掷骰子时，连续 掷出数字i的次数不能超过rollMax[i]（i从1开始编号）。
现在，给你一个整数数组rollMax和一个整数n，请你来计算掷n次骰子可得到的不同点数序列的数量。
假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 模10^9 + 7之后的结果。
示例1:
输入：n = 2, rollMax = [1,1,2,2,2,3]
输出：34
解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 = 34。
示例2:
输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。
示例3:
输入：n = 3, rollMax = [1,1,1,2,2,3]
输出：181
提示：
1 <= n <= 5000rollMax.length == 61 <= rollMax[i] <= 15
这两次比赛leetcode都以排列组合为背景出动态规划的题。动态规划数组为dp[i][k]，i代表总共扔骰子的次数，k代表第i次扔骰子扔到k，即dp[i][k]代表扔i次骰子，并且第i次骰子点数为k的可能序列总数。sumOf(dp[i])为扔i次骰子的所有可能序列数。
考虑特殊的情况。当rollMax[k] > i时，即骰子数k的最大连续次数大于目前扔骰子的次数时，那么第i次扔出骰子数k的可能序列数就直接等于扔i-1次骰子的所有可能序列数了。
再考虑一般情况下dp[i][k]与dp[i-1][k]之间的关系，由于数字k连续出现的次数不能大于rollMax[k]，也就是说如果要在第i次扔出数字k，则要求当第i-1次也扔出骰子数k时，k的连续次数不大于rollMax[k]-1。换言之，dp[i][k]的总可能序列数等于sumOf(dp[i-1])减去dp[i-1][k]中k连续次数正好等于rollMax[k]的序列总数。
如果dp[i-1][k]中k连续次数正好等于rollMax[k]，则说明从i-1-rollMax[k]+1到 i-1的部分扔出的骰子数都是k，并且第i-1-rollMax[k]次扔骰子还不能扔到点数k，否则k的连续次数就会大于rollMax[k]了。因此出现的可能序列总数就等于sumOf(dp[i-1-rollMax[k]]) - dp[i-1-rollMax[k]][k] ，即前i-1-rollMax[k]的所有可能序列数，减去第i-1-rollMax[k]次扔出骰子k的可能序列数。
考虑特殊情况rollMax[k] == i-1时，即骰子点数k的最大连续次数恰好等于i-1。那么这种情况下，第i-1次时骰子数k连续出现rollMax[k]次的可能序列只有一种。但是dp[i-1-rollMax[k]] = dp[0]初始化是0，因此这种情况要单独写。
最后的问题就是取模。减法的取模与加法的取模有所不同。在编程时不能写成下面这样：
a=(a%c);
b=(b%c);
ans=( a - b )%c;
因为可能会出现a比b小的情况，这样得出来的结果就不对了。
因此需要写成下面👇这样：
a=a%c;
b=b%c;
ans = ( a - b + c ) % c;
c%c的结果是0，因此不会影响。还能保证ans不会是负数。
在分析的时候都是从下标1开始的，写代码时注意下标减一。
class Solution {
public:
long long int sumOf(long long int arr[]){
int N = pow(10,9)+7;
return (arr[0]%N+arr[1]%N+arr[2]%N+arr[3]%N+arr[4]%N+arr[5]%N)%N;
}
int dieSimulator(int n, vector<int>& rollMax) {
int N = pow(10,9)+7;
long long int dp[5005][6] = {0};
for(int i=0;i<6;i++){
dp[1][i] = 1;
}
for(int i=2;i<=n;i++){
for(int j=1;j<=6;j++){
if(rollMax[j-1]>=i){
dp[i][j-1] = sumOf(dp[i-1]);
}
else if(rollMax[j-1] < i-1){
dp[i][j-1] = ((sumOf(dp[i-1]) - sumOf(dp[i-1-rollMax[j-1]]) + N)%N + dp[i-1-rollMax[j-1]][j-1]%N )%N;
}
else{
dp[i][j-1] = sumOf(dp[i-1]) - 1;
}
}
}
return sumOf(dp[n]);
}
};
题目链接：https://leetcode-cn.com/contest/weekly-contest-158/problems/dice-roll-simulation/
