数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 骰子模拟
假设一个骰子模拟器在每次掷骰时生成 1 到 6 之间的随机数。我们希望为生成器引入一个约束条件，即它不能连续掷出数字 i 超过 rollMax[i]（从 1 开始索引）次。假设我们有一个整数数组 rollMax 和一个整数 n，我们需要返回可以使用恰好 n 次掷骰获得的不同序列的数量。如果至少有一个元素彼此不同，则两个序列被认为是不同的。因此，如果 n 为 2，则 rollMax = [1,1,2,2,2,3]，则输出将为 34。因此，骰子将掷 2 次，如果没有约束，骰子上将有 6*6 = 36 种可能的组合，在这种情况下，数字 1 和 2 最多连续出现一次，因此序列 (1,1) 和 (2,2) 不会出现。所以最终答案将是 36 – 2 = 34。
为了解决这个问题，我们将遵循以下步骤：
- 创建一个名为 dfs() 的方法，它将接收 dieLeft、last、currLen、数组 r 和矩阵 dp 作为参数。
- 如果 dieLeft = 0，则返回 1。
- 如果 dp[dieLeft][last][currLen] 不为 -1，则返回 dp[dieLeft, last, currLen]。
- 计数器 := 0
- 对于 i 的范围从 0 到 6
- 如果 i = last 且 r[i] = currLen，则跳过下一部分并进行下一次迭代。
- 计数器 := dfs(dieLeft – 1, i, 当 i = last 时 currLen + 1，否则为 1, r, dp)
- dp[dieLeft, last, currLen] := 计数器
- 返回 dp[dieLeft, last, currLeft]
- 主方法将如下所示：
- 创建一个名为 dp 的 3D 数组，其阶数为 (n + 1) x 6 x 16，并将其全部填充为 -1。
- 返回 dfs(n, 0, 0, rollMax, dp)
让我们看看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
class Solution {
public:
int dfs(int dieLeft, int last, int currLen, vector <int> &r,vector < vector < vector <int> > > &dp){
if(dieLeft == 0){
return 1;
}
if(dp[dieLeft][last][currLen]!=-1)return dp[dieLeft][last][currLen];
int counter = 0;
for(int i =0;i<6;i++){
if(i==last && r[i] == currLen)continue;
counter = (counter%mod + (dfs(dieLeft-1,i,i==last?currLen+1:1,r,dp))%mod)%mod;
}
dp[dieLeft][last][currLen] = counter%mod;
return dp[dieLeft][last][currLen]%mod;
}
int dieSimulator(int n, vector<int>& rollMax) {
vector < vector < vector <int> > > dp(n+1, vector < vector <int> > (6, vector <int>(16, -1)));
return dfs(n,0,0,rollMax, dp)%mod;
}
};
main(){
vector<int> v = {1,1,2,2,2,3};
Solution ob;
cout << (ob.dieSimulator(2,v));
}输入
2 [1,1,2,2,2,3]
输出
34
更新于: 2020年4月30日
560 次浏览
广告