1223. 掷骰子模拟 (Hard)
问题描述
有一个骰子模拟器会每次投掷的时候生成一个 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 <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15
解题思路
动态规划
这一题是很明显的动态规划思路,状态定义很好想,状态转移方程也不难确定:
记dp[i][j]
为掷i
次骰子,最后一次结果为j + 1
的可能的组合,要求的答案即dp[n][0] + ... + dp[n][5]
,显然,我们只需排除最后rollMax[j] + 1
次都是j
的情况;
状态转移方程为:
if i <= rollMax[j]
: \(dp[i][j] = \sum\limits_{k = 0}^{5} dp[i - 1][k]\)
else if i == rollMax[j] + 1
: \(dp[i][j] = \sum\limits_{k = 0}^{5} dp[i - 1][k] - 1\)
else
: \(dp[i][j] = \sum\limits_{k = 0}^{5}dp[i - 1][k] - \sum\limits_{k = 0, k\neq j}^{5}dp[i - rollMax[j] - 1][j]\)
记忆化搜索
这里我们从第n
次向第一次倒着考虑,那么我们要关注的几个变量:
- 当前投掷骰子的次数
idx
; - 当前投掷的骰子数字减一,记为
last_num
; - 当前数字往后的最大连续数量,记为
max_len
,例如\(623166\),考虑idx = 5
,那么最大连续数量就是\(2\),这里的max_len
要分等于rollMax[last_num]
和小于rollMax[last_num]
的情况来讨论,小于则可以继续选last_num
,内层递归的max_len
为max_len + 1
;否则必须选其他的数,同时内层递归的max_len
置1;
当前递归的结果应该取下一层递归的结果之和;
边界条件,当idx == 0
时,应该return 1;
cache
数组的三个维度即idx
,last_num
,max_len
,其中max_len <= 15
,所以cache
数组为vector<vector<vector<long>>> cache(n + 1, vector<vector<long>>(16, vector<long>(6, -1)));
代码
动态规划
class Solution {
public:
int dieSimulator(int n, vector<int> &rollMax) {
int mod = 1000000007;
if (n == 1) return 6;
vector<vector<int>> dp(n + 1, vector<int>(6, 0));
for (int i = 0; i < 6; i++) {
dp[0][i] = 1;
dp[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 6; j++) {
if (i <= rollMax[j]) {
dp[i][j] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5]) % mod;
} else if (i == rollMax[j] + 1) {
int tmp_sum = 0;
for (int k = 0; k < 6; k++) {
tmp_sum = (tmp_sum + dp[i - 1][k]) % mod;
}
dp[i][j] = (tmp_sum - 1) % mod;
} else {
int tmp_sum = 0;
int tmp_minus = 0;
for (int k = 0; k < 6; k++) {
tmp_sum = (tmp_sum + dp[i - 1][k]) % mod;
if (k == j) {
continue;
}
tmp_minus = (tmp_minus + dp[i - rollMax[j] - 1][k]) % mod;
}
dp[i][j] = (tmp_sum - tmp_minus + mod) % mod;
}
}
}
int res = 0;
for (int j = 0; j < 6; j++) {
res = (res + dp[n][j]) % mod;
}
return res;
}
};
记忆化搜索
class Solution {
public:
long dfs(int idx, vector<int> &rollMax, int max_len, int last_num, vector<vector<vector<long>>> &cache, int mod) {
if (idx == 0) {
return 1;
}
if (cache[idx][max_len][last_num] >= 0) {
return cache[idx][max_len][last_num] % mod;
}
long res = 0;
if (max_len < rollMax[last_num]) {
for (int i = 0; i < 6; ++i) {
if (i == last_num) {
res += dfs(idx - 1, rollMax, max_len + 1, i, cache, mod);
res %= mod;
} else {
res += dfs(idx - 1, rollMax, 1, i, cache, mod);
res %= mod;
}
}
} else {
for (int i = 0; i < 6; ++i) {
if (i != last_num) {
res += dfs(idx - 1, rollMax, 1, i, cache, mod);
res %= mod;
}
}
}
cache[idx][max_len][last_num] = res % mod;
return cache[idx][max_len][last_num];
}
int dieSimulator(int n, vector<int> &rollMax) {
// 尝试记忆化搜索
vector<vector<vector<long>>> cache(n + 1, vector<vector<long>>(16, vector<long>(6, -1)));
int mod = 1000000007;
return dfs(n, rollMax, 0, 6, cache, mod);
}
};
最新文章
- 关于包含pom.xml的开源项目如何导入
- 《Python核心编程》部分错误纠正(勘误表)(持续更新)
- Qt 获取cmd运行结果
- HTML&;CSS----练习隐藏导航栏(初级)
- NBUT 1635 Explosion(最小顶点覆盖)
- TDE与列级数据加密
- ios 照片编辑的view封装
- 自动运行native2ascii 命令的Bat文件的编写
- MFC CListCtrl得到ctrl,shift多选的行号
- bootstrap使用汇总
- RPC和RMI的区别(Difference Between RPC and RMI)
- Nexus 私有仓库搭建与 Maven 集成
- nodejs http小爬虫
- IPFS:Filecoin和复制证明
- ibatis .net $与#的区别
- idea打开dashboard
- ImageMagick: 6.8.3 升级到 6.8.9 遇到的问题
- 黑马程序员_Java基础视频-深入浅出精华版--PPT 文件列表
- Java位运算符浅析
- Django模板语言的复用
热门文章
- 用了这么多年的 SpringBoot 你知道什么是 SpringBoot 的 Web 类型推断吗?
- CF1779 Least Prefix Sum
- js鼠标轨迹特效
- Redis缓存何以一枝独秀?(2) —— 聊聊Redis的数据过期、数据淘汰以及数据持久化的实现机制
- 01-Tcl基本知识
- 动力节点——day03
- Grafana 系列文章(五):Grafana Explore 查询管理
- 读Java8函数式编程笔记02_流
- Quartz.Net源码Example之Quartz.Examples.AspNetCore
- CentOS即将停止维护,拥抱阿里“龙蜥“(Anolis OS),VMware安装Anolis OS与介绍