class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
}
};
1223. 掷骰子模拟
有一个骰子模拟器会每次投掷的时候生成一个 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原站题解
golang 解法, 执行用时: 20 ms, 内存消耗: 9.7 MB, 提交时间: 2023-02-10 10:17:12
func dieSimulator(n int, rollMax []int) (ans int) {
f := make([][7][16]int, n+1)
for j := 1; j <= 6; j++ {
f[1][j][1] = 1
}
const mod = 1e9 + 7
for i := 2; i <= n; i++ {
for j := 1; j <= 6; j++ {
for x := 1; x <= rollMax[j-1]; x++ {
for k := 1; k <= 6; k++ {
if k != j {
f[i][k][1] = (f[i][k][1] + f[i-1][j][x]) % mod
} else if x+1 <= rollMax[j-1] {
f[i][j][x+1] = (f[i][j][x+1] + f[i-1][j][x]) % mod
}
}
}
}
}
for j := 1; j <= 6; j++ {
for x := 1; x <= rollMax[j-1]; x++ {
ans = (ans + f[n][j][x]) % mod
}
}
return
}
python3 解法, 执行用时: 2016 ms, 内存消耗: 297.6 MB, 提交时间: 2023-02-10 10:16:55
# 动态规划
class Solution:
def dieSimulator(self, n: int, rollMax: List[int]) -> int:
f = [[[0] * 16 for _ in range(7)] for _ in range(n + 1)]
for j in range(1, 7):
f[1][j][1] = 1
for i in range(2, n + 1):
for j in range(1, 7):
for x in range(1, rollMax[j - 1] + 1):
for k in range(1, 7):
if k != j:
f[i][k][1] += f[i - 1][j][x]
elif x + 1 <= rollMax[j - 1]:
f[i][j][x + 1] += f[i - 1][j][x]
mod = 10**9 + 7
ans = 0
for j in range(1, 7):
for x in range(1, rollMax[j - 1] + 1):
ans = (ans + f[n][j][x]) % mod
return ans
golang 解法, 执行用时: 32 ms, 内存消耗: 9.3 MB, 提交时间: 2023-02-10 10:16:27
func dieSimulator(n int, rollMax []int) int {
f := make([][7][16]int, n)
const mod = 1e9 + 7
var dfs func(i, j, x int) int
dfs = func(i, j, x int) int {
if i >= n {
return 1
}
if f[i][j][x] != 0 {
return f[i][j][x]
}
ans := 0
for k := 1; k <= 6; k++ {
if k != j {
ans += dfs(i+1, k, 1)
} else if x < rollMax[j-1] {
ans += dfs(i+1, j, x+1)
}
}
f[i][j][x] = ans % mod
return f[i][j][x]
}
return dfs(0, 0, 0)
}
python3 解法, 执行用时: 1692 ms, 内存消耗: 188 MB, 提交时间: 2023-02-10 10:16:07
# 记忆化搜索，dfs(i, j, x) 表示第i次投掷，点数为j，且连续投掷出j的次数为x的方案数
class Solution:
def dieSimulator(self, n: int, rollMax: List[int]) -> int:
@cache
def dfs(i, j, x):
if i >= n:
return 1
ans = 0
for k in range(1, 7):
if k != j:
ans += dfs(i + 1, k, 1)
elif x < rollMax[j - 1]:
ans += dfs(i + 1, j, x + 1)
return ans % (10 ** 9 + 7)
return dfs(0, 0, 0)
cpp 解法, 执行用时: 120 ms, 内存消耗: 6.6 MB, 提交时间: 2023-02-10 10:13:57
class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
const int divider = 1e9 + 7;
vector<vector<int>> dp(7,vector<int>(16,0));
for (int i = 1; i < 7; ++i) {
dp[i][1] = 1;
}
vector<vector<int>> temp ;//暂时存储上一次投掷后的结果
for (int i = 1; i < n; ++i) {
temp = dp;
for (int j = 1; j < 7; ++j) {
dp[j][1] = 0;
for (int k = 1; k < 7; ++k) {
if (j != k) {
for (int t = 1; t <= rollMax[k-1]; ++t) {
dp[j][1] += temp[k][t];
dp[j][1] %= divider;
}
}
else {
for (int t = 1; t < rollMax[k-1]; ++t) {
dp[j][t + 1] = temp[k][t];
}
}
}
}
}
int sum = 0;
for (int i = 1; i < 7; ++i) {
for (int t = 1; t <= rollMax[i-1]; ++t) {
sum = (sum + dp[i][t]) % divider;
}
}
return sum;
}
};
cpp 解法, 执行用时: 192 ms, 内存消耗: 33.4 MB, 提交时间: 2023-02-10 10:13:46
/**
* dp[n][7][16] 一维：投掷次数，二维：点数（1-6），三维：本次投掷后该点数已连续出现次数
* 最终的结果应该是最后一次投骰子之后，1~6所有可能出现的连续次数对应的情况个数
*
*/
class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
const int divider = 1e9 + 7;
vector<vector<vector<int>>> dp(n,vector<vector<int>>(7,vector<int>(16,0)));//与用三维数组同理
for (int i = 1; i < 7; ++i) {
dp[0][i][1] = 1; // 第一次投掷，连续出现次数都为1
}
for (int i = 1; i < n; ++i) {//第i + 1次投掷
for (int j = 1; j < 7; ++j) {//出现的点数为j
for (int k = 1; k < 7; ++k) {//上一次出现的点数为k
if (j != k) {
for (int t = 1; t <= rollMax[k-1]; ++t) {
dp[i][j][1] += dp[i - 1][k][t];
dp[i][j][1] %= divider;
}
}
else {
for (int t = 1; t < rollMax[k-1]; ++t) {
dp[i][j][t + 1] += dp[i - 1][k][t];
dp[i][j][t + 1] %= divider;
}
}
}
}
}
int sum = 0;
for (int i = 1; i < 7; ++i) {
for (int t = 1; t <= rollMax[i-1]; ++t) {
sum = (sum + dp[n - 1][i][t]) % divider;
}
}
return sum;
}
};