1223 Dice Roll Simulation 掷骰子模拟
问题描述
有一个骰子模拟器会每次投掷的时候生成一个 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：
输入：n = 2, rollMax = [1,1,1,1,1,1]
输出：30
- 示例 3：
输入：n = 3, rollMax = [1,1,1,2,2,3]
输出：181
- 提示：
1 <= n <= 5000rollMax.length == 61 <= rollMax[i] <= 15
思路
- 读题
主要在于连续次数, 可以固定上一轮的骰子序列, 本轮再进行判断
动态规划
上一轮的骰子序列是可以确定的, 则本轮有两种情况:
-
本轮投出与上一轮不同的骰子数, 则连续数为1, 必定可以
-
本轮投出与上一轮相同的骰子数, 则连续值+1, 需要判断
-
注:
F(i,j,k)第i轮投出j时, j的连续出现频次kpj上一轮结尾数字pjr上一轮结尾数字为pj时 pj的连续出现次数
-
示例: n=3, rollMax=[1,1,1,2,2,3]
代码实现
动态规划
class Solution {
/**
* 骰子六个面
*/
private final static int SIZE = 6;
/**
* 投出数可以连续出现次数 最多15次
*/
private final static int ROLL_SIZE = 16;
/**
* 取模数
*/
private final static int MOD = (int) 1e9 + 7;
public int dieSimulator(int n, int[] rollMax) {
// [i][j][k] 第i轮投出j时j的连续出现频次k
int[][][] dp = new int[n + 1][SIZE][ROLL_SIZE];
// 第1轮 投出数字j 且其出现频次为1
for (int j = 0; j < SIZE; j++) {
dp[1][j][1] = 1;
}
// 第i轮 投出数字为j
// 它的出现频次取决于两个:
// 1. 其他数字pj的组合 j作为结尾(这样就绝对不会出现连续)
// 2. 自己连续序列 需要判断RollMax[j]是否限制
for (int i = 2; i <= n; i++) {
for (int j = 0; j < SIZE; j++) {
for (int pj = 0; pj < SIZE; pj++) {
// 先搜集其他组合 自己作为结尾的出现频次
if (pj != j) {
// pjr 表示pj数字的组合中pj连续出现次数
for (int pjr = 1; pjr <= rollMax[pj]; pjr++) {
// 本轮己方连续出现一次组合 += 上一轮其他数字的所有组合
dp[i][j][1] += dp[i - 1][pj][pjr];
dp[i][j][1] %= MOD;
}
// 在查看自己的连续序列 是否达到限制
} else {
// jr 表示j数字的组合中j连续出现次数
for (int jr = 1; jr < rollMax[j]; jr++) {
// 本轮该数字j连续出现频次(加上本次投出j) += 上一轮连续出现频次
dp[i][j][jr + 1] += dp[i - 1][j][jr];
dp[i][j][jr + 1] %= MOD;
}
}
}
}
}
int ans = 0;
// 获取第n轮 投出数字j所有出现k频次
for (int j = 0; j < SIZE; j++) {
for (int k = 1; k <= rollMax[j]; k++) {
ans += dp[n][j][k];
ans %= MOD;
}
}
return ans;
}
}