有一個骰子模擬器會每次投擲的時候生成一個 1到 6 的隨機(jī)數(shù)。
不過我們在使用它時有個約束，就是使得投擲骰子時，連續(xù) 擲出數(shù)字 i的次數(shù)不能超過 rollMax[i]（i 從 1 開始編號）。
現(xiàn)在，給你一個整數(shù)數(shù)組 rollMax 和一個整數(shù) n，請你來計(jì)算擲 n 次骰子可得到的不同點(diǎn)數(shù)序列的數(shù)量。
假如兩個序列中至少存在一個元素不同，就認(rèn)為這兩個序列是不同的。由于答案可能很大，所以請返回 模 10^9 + 7 之后的結(jié)果。

示例1:

輸入：n = 2, rollMax = [1,1,2,2,2,3]
輸出：34
解釋：我們擲 2 次骰子，如果沒有約束的話，共有 6 * 6 = 36 種可能的組合。但是根據(jù) rollMax 數(shù)組，數(shù)字 1 和 2 最多連續(xù)出現(xiàn)一次，所以不會出現(xiàn)序列 (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 <= 5000
• rollMax.length == 6
• 1 <= rollMax[i] <= 15

這兩次比賽leetcode都以排列組合為背景出動態(tài)規(guī)劃的題。動態(tài)規(guī)劃數(shù)組為dp[i][k]，i代表總共扔骰子的次數(shù)，k代表第i次扔骰子扔到k，即dp[i][k]代表扔i次骰子，并且第i次骰子點(diǎn)數(shù)為k的可能序列總數(shù)。sumOf(dp[i])為扔i次骰子的所有可能序列數(shù)。

考慮特殊的情況。當(dāng)rollMax[k] > i時，即骰子數(shù)k的最大連續(xù)次數(shù)大于目前扔骰子的次數(shù)時，那么第i次扔出骰子數(shù)k的可能序列數(shù)就直接等于扔i-1次骰子的所有可能序列數(shù)了。

再考慮一般情況下dp[i][k]與dp[i-1][k]之間的關(guān)系，由于數(shù)字k連續(xù)出現(xiàn)的次數(shù)不能大于rollMax[k]，也就是說如果要在第i次扔出數(shù)字k，則要求當(dāng)?shù)?code>i-1次也扔出骰子數(shù)k時，k的連續(xù)次數(shù)不大于rollMax[k]-1。換言之，dp[i][k]的總可能序列數(shù)等于sumOf(dp[i-1])減去dp[i-1][k]中k連續(xù)次數(shù)正好等于rollMax[k]的序列總數(shù)。

如果dp[i-1][k]中k連續(xù)次數(shù)正好等于rollMax[k]，則說明從i-1-rollMax[k]+1到 i-1的部分扔出的骰子數(shù)都是k，并且第i-1-rollMax[k]次扔骰子還不能扔到點(diǎn)數(shù)k，否則k的連續(xù)次數(shù)就會大于rollMax[k]了。因此出現(xiàn)的可能序列總數(shù)就等于sumOf(dp[i-1-rollMax[k]]) - dp[i-1-rollMax[k]][k] ，即前i-1-rollMax[k]的所有可能序列數(shù)，減去第i-1-rollMax[k]次扔出骰子k的可能序列數(shù)。

考慮特殊情況rollMax[k] == i-1時，即骰子點(diǎn)數(shù)k的最大連續(xù)次數(shù)恰好等于i-1。那么這種情況下，第i-1次時骰子數(shù)k連續(xù)出現(xiàn)rollMax[k]次的可能序列只有一種。但是dp[i-1-rollMax[k]] = dp[0]初始化是0，因此這種情況要單獨(dú)寫。

最后的問題就是取模。減法的取模與加法的取模有所不同。在編程時不能寫成下面這樣：

a=(a%c);
b=(b%c);
ans=( a - b )%c;

因?yàn)榭赡軙霈F(xiàn)a比b小的情況，這樣得出來的結(jié)果就不對了。
因此需要寫成下面??這樣：

a=a%c;
b=b%c;
ans = ( a - b + c ) % c;

c%c的結(jié)果是0，因此不會影響。還能保證ans不會是負(fù)數(shù)。

在分析的時候都是從下標(biāo)1開始的，寫代碼時注意下標(biāo)減一。

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/