Leetcode.1223 掷骰子模拟
题目链接
Leetcode.1223 掷骰子模拟 Rating : 2008
题目描述
有一个骰子模拟器会每次投掷的时候生成一个 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 1 <= n <= 5000 1<=n<=5000
- r o l l M a x . l e n g t h = = 6 rollMax.length == 6 rollMax.length==6
- 1 < = r o l l M a x [ i ] < = 15 1 <= rollMax[i] <= 15 1<=rollMax[i]<=15
分析:
使用 动态规划 的方式求解。
我们定义
f
(
i
,
j
,
t
i
m
e
s
)
f(i,j,times)
f(i,j,times) 为投掷了 i
次骰子,并且第 i
个骰子的点数是 j
,且这个 j
的连续出现次数是 times
的不同序列数量。
按照定义,最终返回的结果为 f ( n , 1 , 1 ) + f ( n , 1 , 2 ) + . . . f ( n , 1 , r o l l M a x [ 0 ] ) . . . f ( n , 2 , 1 ) + f ( n , 2 , 2 ) . . . + f ( n , 2 , r o l l M a x [ 1 ] + . . . f ( n , 6 , r o l l M a x [ 5 ] ) f(n,1,1) + f(n,1,2) + ...f(n,1,rollMax[0])...f(n,2,1)+f(n,2,2)...+f(n,2,rollMax[1] + ...f(n,6,rollMax[5]) f(n,1,1)+f(n,1,2)+...f(n,1,rollMax[0])...f(n,2,1)+f(n,2,2)...+f(n,2,rollMax[1]+...f(n,6,rollMax[5])。
即 ∑ j = 1 6 ∑ t i m e s = 1 r o l l M a x [ j − 1 ] f ( n , j , t i m e s ) \sum_{j=1}^{6}\sum_{times=1}^{rollMax[j-1]}f(n,j,times) ∑j=16∑times=1rollMax[j−1]f(n,j,times)。
状态转移:
- 当 当前点
k
不等于 前一个点j
时, f ( i , k , 1 ) = ( f ( i , k , 1 ) + f ( i − 1 , j , t i m e s ) ) m o d 1 0 9 + 7 f(i,k,1) = (f(i,k,1)+f(i-1,j,times)) mod 10^9+7 f(i,k,1)=(f(i,k,1)+f(i−1,j,times))mod109+7 - 当 当前点
k
等于 前一个点j
并且times+1
小于等于rollMax[j-1]
时, f ( i , j , t i m e s + 1 ) = ( f ( i , j , t i m e s + 1 ) + f ( i − 1 , j , t i m e s ) ) m o d 1 0 9 + 7 f(i,j,times+1) = (f(i,j,times+1) + f(i-1,j,times)) mod 10^9+7 f(i,j,times+1)=(f(i,j,times+1)+f(i−1,j,times))mod109+7
时间复杂度: O ( n ∗ 36 ∗ 15 ) O(n * 36 * 15) O(n∗36∗15)
C++代码:
const int MOD = 1e9+7;
using LL = long long;
class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
int f[n+1][7][16];
memset(f,0,sizeof f);
//初始化只投掷一次骰子的情况
for(int i = 1;i <= 6;i++){
f[1][i][1] = 1;
}
for(int i = 2;i <= n;i++){
for(int j = 1;j <= 6;j++){
for(int times = 1;times <= rollMax[j-1];times++){
for(int k = 1;k <= 6;k++){
if(j != k) f[i][k][1] = (f[i][k][1] + f[i-1][j][times])%MOD;
else if(times + 1 <= rollMax[j - 1]){
f[i][j][times+1] = (f[i][j][times+1] + f[i-1][j][times])%MOD;
}
}
}
}
}
LL ans = 0;
//统计总的数量
for(int j = 1;j <= 6;j++){
for(int times = 1;times <= rollMax[j-1];times++) ans += f[n][j][times];
}
return ans % MOD;
}
};
Java代码:
class Solution {
private final int MOD = 1000_000_000+7;
public int dieSimulator(int n, int[] rollMax) {
int [][][] f = new int[n+1][7][16];
for(int i = 1;i <= 6;i++){
f[1][i][1] = 1;
}
for(int i = 2;i <= n;i++){
for(int j = 1;j <= 6;j++){
for(int times = 1;times <= rollMax[j-1];times++){
for(int k = 1;k <= 6;k++){
if(j != k) f[i][k][1] = (f[i][k][1] + f[i-1][j][times])%MOD;
else if(times + 1 <= rollMax[j - 1]){
f[i][j][times+1] = (f[i][j][times+1] + f[i-1][j][times])%MOD;
}
}
}
}
}
long ans = 0;
for(int j = 1;j <= 6;j++){
for(int times = 1;times <= rollMax[j-1];times++) ans += f[n][j][times];
}
return (int)(ans % MOD);
}
}
相关文章
- 第五章 模拟跳转充值界面以及requestCode和resultCode的解释 2.8
- 【C++】string类的模拟实现
- ext4 io hung模拟脚本
- 5个时间序列预测的深度学习模型对比总结:从模拟统计模型到可以预训练的无监督模型
- 模拟数据在实际场景中的应用
- 利用Teensy进行EM410x卡模拟以及暴力破解EM410X类门禁系统可行性猜想
- 25字中文文章标题:Linux命令模拟回车,轻松提升操作效率(linux命令模拟回车)
- PHP模拟SQLServer的两个日期处理函数
- winform模拟鼠标按键的具体实现
- javascript实现的弹出层背景置灰-模拟(easyuidialog)
- python3模拟百度登录并实现百度贴吧签到示例分享(百度贴吧自动签到)
- 基于WebClient实现Http协议的Post与Get对网站进行模拟登陆和浏览实例