假设骰子模拟器为每个卷生成一个1到6的随机数。我们要向生成器引入一个约束，以使其不能连续滚动i的次数不超过rollMax [i]（1索引）。假设我们有一个整数数组rollMax和一个整数n，我们必须返回可以用精确的n个roll获得的不同序列的数量。如果至少一个元素彼此不同，则认为这两个序列不同。因此，如果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
对于0到6的i
如果i =最后并且r [i] = currLen，则跳过下一部分并进行下一次迭代
计数器：= dfs（dieLeft – 1，i，当i = last时为currLen + 1，否则为1，r，dp）
dp [dieLeft，last，currLen]：=计数器
return 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