力扣題庫-擲骰子模擬詳細解析

題目如下：

有一個骰子模擬器會每次投擲的時候生成一個 1 到 6 的隨機數。

不過我們在使用它時有個約束，就是使得投擲骰子時，連續?擲出數字?i?的次數不能超過?rollMax[i]（i?從 1 開始編號）。

現在，給你一個整數數組?rollMax?和一個整數?n，請你來計算擲?n?次骰子可得到的不同點數序列的數量。

假如兩個序列中至少存在一個元素不同，就認為這兩個序列是不同的。

由于答案可能很大，所以請返回?模?10^9 + 7?之后的結果。

限制如下

1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

解析如下：

在不考慮rollMax?限制情況下

若第1次：投擲1~6，連續1次點數相同，則每個點數各有1種，即d[1][i][1] = 1（初始值），定義i為

????????????????第一次可能投擲出的點數，X為第一次已經投擲出的點數，則第一次投擲結果表示為? X?

若第2次：投擲1~6，連續2次點數相同，則每個點數各有1種，即d[2][i][2] = 1，i為第二次可能投擲

????????????????出的點數，Y為第二次已經投擲出的點數，則兩次投擲出的結果表示為 XY，且X=Y，

????????????????則d[2][i][2] = d[1][i][1] ；

????????????????投擲1~6，連續1次點數相同，則兩次投擲出的結果表示為 XY，且X != Y，在Y確定時，

? ? ? ? ? ? ? ? 只需考慮前一次的情況，即X的值，X有6-1種選擇，即d[2][i][1] = d[1][j][1] * 5 ，此處

????????????????*5表示第一次投擲d[1][i][1] 6種情況減去X=Y這種情況的累加，

????????????????d[2][i][1] =?d[1][a][1]+d[1][b][1]+d[1][c][1]+d[1][d][1]+d[1][e][1]；

若第3次：投擲1~6，連續3次點數相同，則每個點數各有1種，即d[3][i][3] = 1，i為第三次可能投擲

????????????????出的點數，Z為第三次已經投擲出的點數，則三次投擲出的結果表示為 XYZ，X=Y=Z，

? ? ? ? ? ? ? ? 在Z確定時，只需要考慮前兩次的投擲情況，即XY的值，因為X=Y，所以只考慮第二次

????????????????投擲1~6，連續2次點數相同的情況即d[2][i][2]的情況，又因為Z?= Y，所以Y只有一種選

????????????????擇，所以d[3][i][3] =?d[2][i][2] = d[1][i][1]；

????????????????投擲1~6，連續2次點數相同，則三次投擲出的結果表示為 XYZ，且Z?= Y != X，在Z

????????????????確定時，只需要考慮前兩次的投擲情況，即XY的值，因為Y != X，所以只考慮第二次

????????????????投擲1~6，連續1次點數相同的情況即d[2][i][1]的情況，

????????????????又因為Z?= Y，所以Y只有一種選擇，所以d[3][i][2] =?d[2][i][1]；

????????????????投擲1~6，連續1次點數相同，則三次投擲出的結果表示為 XYZ，且Z != Y，Y與X可相等

????????????????可不等，

????????????????先考慮Y != X情況，在Z確定時，只需要考慮前兩次的投擲情況，即XY的值，因為Y != ????????????????X，所以只考慮第二次投擲1~6，連續1次點數相同的情況即d[2][i][1]的情況，

????????????????又因為Z != Y，所以Y有6-1種選擇，

????????????????即d[3][i][1] =? d[2][i][1] * 5 = d[2][a][1]+d[2][b][1]+d[2][c][1]+d[2][d][1]+d[2][e][1]；

? ? ? ? ? ? ? ? 再考慮Y=X情況，在Z確定時，只需要考慮前兩次的投擲情況，即XY的值，

????????????????因為Y = X，所以只考慮第二次投擲1~6，連續2次點數相同的情況即d[2][i][2]的情況，

????????????????又因為Z != Y，所以Y有6-1種選擇，

? ? ? ? ? ? ? ? 即d[3][i][1] =?d[2][i][2] * 5 =?d[2][a][2]+d[2][b][2]+d[2][c][2]+d[2][d][2]+d[2][e][2]，注意從

? ? ? ? ? ? ? ? 此處開始就需要考慮rollMax?的影響，暫時先忽略，

? ? ? ? ? ? ? ? 將上述兩種情況相加可得：d[3][i][1] =?d[2][a][1]+d[2][b][1]+d[2][c][1]+d[2][d][1]+d[2][e][1] +?d[2][a][2]+d[2][b][2]+d[2][c][2]+d[2][d][2]+d[2][e][2]，可以轉變為下面的代碼

d[3][i][1] = 0;
for(int v = 1; v <= 6; v++)
{for(int k = 1; k <= 2; k++){if(v != i){d[3][i][1] += d[2][v][k];}}
}

由上述幾種投擲情況，可以發現，連續1次點數相同情況特殊，需要找上一次投擲的所用情況中排除，而超過1次點數相同情況只需要找上一次投擲中對應次數-1的結果即可，總結如下

第n次投擲1~6，連續1次點數相同的即d[n][i][1]的值為第n-1次投擲連續1次，2次到n-1次點數相同的所有情況減去每種情況下點數與i相同的情況的總和，如下

for(int v = 1; v <= 6; v++)
{for(int k = 1; k <= n - 1; k++){if(v != i){d[n][i][1] += d[n-1][v][k];}}
}
帶入n = 2，結果正確

第n次投擲1~6，連續k次點數相同（k>1）的即d[n][i][k]的值為第n-1次投擲連續k-1次點數相同的6種情況中第n-1次投擲與第n次投擲結果相同的一種情況，即d[n][i][k] = d[n - 1][i][k-1]

由上述總結可以得到如下的忽略rollMax?的代碼

const int MOD = 1000000007;int DieSimulator2(int n)
{//狀態 d[i][j][k] 表示已經完成了 i 次擲骰子，第 i 次擲的是 j，并且已經連續擲了 k 次 j 的方案數。//投擲從1開始算，所以為 n+1int[][][] d = new int[n + 1][][];for (int i = 0; i <= n; i++){d[i] = new int[6][];for (int j = 0; j < 6; j++){//此處的16表示最多連續15次，由1 <= rollMax[i] <= 15得到d[i][j] = new int[16];}}//第一次投擲出且連續擲出j的方案數只能是1，用0~5來代替投擲出1~6的點數for (int j = 0; j < 6; j++){d[1][j][1] = 1;}//第一次投擲結果已知，從第二次開始for(int i = 2; i <= n; i++){//本次投擲的結果for(int j = 0; j < 6; j++){//本次投擲的連續次數for(int k = 1; k <= n; k++){if(k != 1){//本次投擲連續次數不為1，結果為i-1次投擲中，結果為j且連續k-1次的情況d[i][j][k] += d[i - 1][j][k - 1];d[i][j][k] %= MOD;}else{//本次投擲連續次數為1，結果為i-1次投擲中，結果不為j，連續次數隨意的情況總和//p為i-1次投擲的結果for (int p = 0; p < 6; p++){//lk為i-1次投擲結果的連續次數，lk不能超過ifor (int lk = 1; lk < i; lk++){//j與p不等情況的累加if(j != p){d[i][j][1] += d[i - 1][p][lk]; d[i][j][1] %= MOD;}}}}}}}int res = 0;for (int j = 0; j < 6; j++){for (int k = 1; k <= n; k++){res = (res + d[n][j][k]) % MOD;}}return res;
}

現在開始考慮rollMax的限制條件，替換其實很簡單，就是在對投擲點數的連續次數的循環上加上限制即可，比如在計算本次連續投擲次數時 for(int k = 1; k <= n; k++) //本次投擲的連續次數，原先的限制為連續次數不能超過總投擲次數，改為 for(int k = 1; k <= rollMax[j]; k++)，不能超過rollMax對應值限制的次數即可，以及在計算本次投擲連續次數為1時，使用上一次投擲情況的地方?for (int lk = 1; lk < i; lk++) //lk為i-1次投擲結果的連續次數，原限制為連續次數不能超出i-1的投擲次數，改為for (int lk = 1; lk <= rollMax[p]; lk++)，變為不能超過rollMax上次投擲值對應限制的次數即可，最后在計算總數時，一樣加上限制即可。

添加限制后的代碼如下

const int MOD = 1000000007;public int DieSimulator(int n, int[] rollMax)
{//狀態 d[i][j][k] 表示已經完成了 i 次擲骰子，第 i 次擲的是 j，并且已經連續擲了 k 次 j 的方案數。//投擲從1開始算，所以為 n+1int[][][] d = new int[n + 1][][];for (int i = 0; i <= n; i++){d[i] = new int[6][];for (int j = 0; j < 6; j++){//此處的16表示最多連續15次，由1 <= rollMax[i] <= 15得到d[i][j] = new int[16];}}//第一次投擲出且連續擲出j的方案數只能是1，用0~5來代替投擲出1~6的點數for (int j = 0; j < 6; j++){d[1][j][1] = 1;}//第一次投擲結果已知，從第二次開始for(int i = 2; i <= n; i++){//本次投擲的結果for(int j = 0; j < 6; j++){//本次投擲的連續次數for(int k = 1; k <= rollMax[j]; k++){if(k != 1){//本次投擲連續次數不為1，結果為i-1次投擲中，結果為j且連續k-1次的情況d[i][j][k] += d[i - 1][j][k - 1];d[i][j][k] %= MOD;}else{//本次投擲連續次數為1，結果為i-1次投擲中，結果不為j，連續次數隨意的情況總和//p為i-1次投擲的結果for (int p = 0; p < 6; p++){//lk為i-1次投擲結果的連續次數for (int lk = 1; lk <= rollMax[p]; lk++){//j與p不等情況的累加，且上次投擲連續次數不能超過當前投擲次數if(j != p && lk < i){d[i][j][1] += d[i - 1][p][lk];d[i][j][1] %= MOD;}}}}}}}int res = 0;for (int j = 0; j < 6; j++){for (int k = 1; k <= rollMax[j]; k++){res = (res + d[n][j][k]) % MOD;}}return res;
}

到這，解析就結束了，當然還有優化空間，但這已經石是我自己研究出來的結果了