मान लीजिए कि एक डाई सिम्युलेटर प्रत्येक रोल के लिए 1 से 6 तक एक यादृच्छिक संख्या उत्पन्न करता है। हम जनरेटर के लिए एक बाधा पेश करना चाहते हैं जैसे कि यह लगातार बार रोलमैक्स [i] (1-अनुक्रमित) से अधिक संख्या को रोल नहीं कर सकता है। विचार करें कि हमारे पास पूर्णांक रोलमैक्स और एक पूर्णांक n की एक सरणी है, हमें अलग-अलग अनुक्रमों की संख्या वापस करनी होगी जिन्हें सटीक n रोल के साथ प्राप्त किया जा सकता है। दो अनुक्रम अलग माने जाते हैं यदि कम से कम एक तत्व एक दूसरे से भिन्न होता है। तो अगर n 2 है, तो रोलमैक्स =[1,1,2,2,2,3], तो आउटपुट 34 होगा। तो मरने पर 2 रोल होंगे, अगर कोई बाधा नहीं है, तो पासे पर हैं 6*6 =36 संभावित संयोजन, इस स्थिति में संख्या 1 और 2 लगातार एक बार अधिक से अधिक दिखाई देते हैं, इसलिए क्रम (1,1) और (2,2) नहीं हो सकते। तो अंतिम उत्तर 36 - 2 =34 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- डीएफएस () नामक एक विधि बनाएं, इसमें डाईलेफ्ट, लास्ट, करलेन, एरे आर और मैट्रिक्स डीपी लगेगी
- यदि dieLeft =0 है, तो 1 लौटाएं
- यदि dp[dieLeft][last][currLen] -1 नहीं है, तो dp[dieLeft, last, currLen] पर वापस लौटें।
- काउंटर:=0
- मैं के लिए 0 से 6 की सीमा में
- यदि i =अंतिम और r[i] =currLen, तो अगला भाग छोड़ें और अगले पुनरावृत्ति के लिए जाएं
- काउंटर:=dfs(dieLeft-1, i, currLen + 1 जब i =लास्ट, अन्यथा 1, r, dp)
- dp[dieLeft, last, currLen] :=काउंटर
- रिटर्न dp[dieLeft, last, currLeft]
- मुख्य विधि इस प्रकार होगी -
- dp ऑफ़ ऑर्डर (n + 1) x 6 x 16 नामक एक 3D सरणी बनाएं और इसे -1 से भरें
- रिटर्न डीएफएस (एन, 0, 0, रोलमैक्स, डीपी)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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