力扣题库-掷骰子模拟详细解析
题目如下：
有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。
不过我们在使用它时有个约束，就是使得投掷骰子时，连续 掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。
现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。
假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。
由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。
限制如下
1 <= n <= 5000rollMax.length == 61 <= 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+1
int[][][] 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不能超过i
for (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+1
int[][][] 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;
}到这，解析就结束了，当然还有优化空间，但这已经石是我自己研究出来的结果了