题目描述
leetcode 困难题
有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。
不过我们在使用它时有个约束，就是使得投掷骰子时，连续 掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。
现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。
假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。
示例1：
1
2
3
| 输入：n = 2, rollMax = [1,1,2,2,2,3]
输出：34
解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 = 34。
|
提示1：
1
2
3
| 1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15
|
动态规划
定义 $dp[i][j]$ 表示第 $i$ 次掷骰子结果点数为 $j$ 的序列个数，那么答案为 $\sum\limits_{j=1}^6 dp[n][j]$ 。
先不考虑连续点数上限的限制，那么 $dp[i][j] = \sum\limits_{k=1}^6dp[i-1][k]$ 。此时只需要再减去以 $j$ 点数结尾并刚好超过 $rollMax[j-1]$ 点数的序列个数即可。
举例说明，设 $j = 3, rollMax[3] = 4$ ，考虑 $dp[7][3]$ ，也就是第 $7$ 次掷出 $3$ 时，此时连续出现 $5$ 个 $3$ 的序列个数为多少。显然该序列只会有一种形式，也就是 $x_1x_233333$，其中 $x_2$ 为不等于 $3$ 的任意点数，该序列的数量即 $dp[2][1] + dp[2][2] + dp[2][4] + dp[2][5] + dp[2][6]$。
也就是说，对于 $dp[i][j]$，我们只需要在上面累加的基础上再减去 $\sum\limits_{k=1\&k!=j}^6dp[i - rollMax[j - 1] - 1][k]$ 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
private final int MOD = (int)(1e9 + 7);
public int dieSimulator(int n, int[] rollMax) {
long[][] dp = new long[n + 2][7];
dp[0][0] = 1;
for(int i = 1; i <= n + 1; i++){
for(int j = 1; j <= 6; j++){
for(int k = 0; k <= 6; k++){
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
if(i < n + 1 && i > rollMax[j - 1]){
for(int k = 0; k <= 6; k++){
if(k == j){
continue;
}
dp[i][j] = dp[i][j] - dp[i - rollMax[j - 1] - 1][k];
if(dp[i][j] <= 0){
dp[i][j] += MOD;
}
}
}
}
}
return (int)dp[n + 1][1];
}
}
|
还有另一种更暴力，但是也较为繁琐的解法。
定义 $dp[i][j][k]$ 表示第 $i$ 次掷骰子结果点数为 $j$ 且此时已经连续出现了 $k$ 次 $j$ 的序列个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
private final int MOD = (int)(1e9 + 7);
public int dieSimulator(int n, int[] rollMax) {
long[][][] dp = new long[n + 1][7][16];
for(int i = 1; i <= 6; i++){
dp[1][i][1] = 1;
}
for(int i = 2; i <= n; i++){
for(int j = 1; j <= 6; j++){
for(int k = 1; k <= 15; k++){
for(int p = 1; p <= 6; p++){
if(j == p && k <= rollMax[j - 1]){
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][p][k - 1]) % MOD;
continue;
}
if(j != p){
dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][k]) % MOD;
}
}
}
}
}
long ans = 0;
for(int j = 1; j <= 6; j++){
for(int k = 1; k <= rollMax[j - 1]; k++){
ans = (ans + dp[n][j][k]) % MOD;
}
}
return (int)ans;
}
}
|