ধরুন একটি ডাই সিমুলেটর প্রতিটি রোলের জন্য 1 থেকে 6 পর্যন্ত একটি এলোমেলো সংখ্যা তৈরি করে। আমরা জেনারেটরে একটি সীমাবদ্ধতা প্রবর্তন করতে চাই যাতে এটি ধারাবাহিক বার 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, array r এবং matrix dp লাগবে
- যদি dieLeft =0, তাহলে 1 ফেরত দিন
- যদি dp[dieLeft][last][currLen] -1 না হয়, তাহলে dp[dieLeft, last, currLen] ফেরত দিন।
- কাউন্টার :=0
- আমি 0 থেকে 6 রেঞ্জের জন্য
- যদি i =শেষ এবং r[i] =currLen, তাহলে পরবর্তী অংশটি এড়িয়ে যান এবং পরবর্তী পুনরাবৃত্তির জন্য যান
- counter :=dfs(dieLeft – 1, i, currLen + 1 when i =last, অন্যথায় 1, r, dp)
- dp[dieLeft, last, currLen] :=কাউন্টার
- রিটার্ন dp[dieLeft, last, currLeft]
- প্রধান পদ্ধতি হবে − এর মত
- ডিপি অফ অর্ডার (n + 1) x 6 x 16 নামে একটি 3D অ্যারে তৈরি করুন এবং এটি -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
