資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告