C ++中的骰子滚动模拟

假设骰子模拟器为每个卷生成一个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