मान लीजिए कि एलिस और बॉब दो व्यक्ति हैं, वे पत्थरों के ढेर के साथ अपना खेल जारी रख रहे हैं। एक पंक्ति में ढेरों ढेर लगाए गए हैं, और प्रत्येक ढेर में एक सरणी ढेर में पत्थरों की एक धनात्मक पूर्णांक संख्या है [i]। खेल का हमारा उद्देश्य सबसे अधिक पत्थरों के साथ समाप्त करना है। ऐलिस और बॉब मोड़ लेते हैं, ऐलिस पहले शुरू करती है। प्रारंभ में, एम =1. प्रत्येक खिलाड़ी की बारी पर, वह खिलाड़ी पहले एक्स शेष ढेर में सभी पत्थरों को ले सकता है, यहां 1 <=एक्स <=2 एम। फिर, हम एम =अधिकतम (एम, एक्स) सेट करते हैं। खेल समाप्त होता है जब कोई पत्थर नहीं छोड़ा जाता है। तो यदि बवासीर =[2,7,9,4,4], तो उत्पादन 10 होगा। ऐसा इसलिए है क्योंकि यदि ऐलिस शुरुआत में एक ढेर लेता है, तो बॉब दो ढेर लेता है, फिर ऐलिस 2 ढेर लेता है। ऐलिस के हाथ में कुल 2+4+4=10 ढेर लग सकते हैं। यदि ऐलिस शुरुआत में दो ढेर लेता है, तो बॉब शेष तीनों ढेर ले सकता है। इस मामले में, ऐलिस को 2 + 7 =9 ढेर मिलते हैं। इसलिए हमें रिटर्न 10 मिलेगा क्योंकि यह बड़ा है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- हल नामक एक पुनरावर्ती फ़ंक्शन बनाएं, जो सरणी, i, m और dp नामक एक मैट्रिक्स लेगा।
- अगर i>=एआर का आकार, तो वापस 0
- अगर dp[i, m] -1 नहीं है, तो dp[i, m] लौटाएं
- यदि i – 1 + 2m>=सरणी का आकार, तो वापसी arr[i]
- op :=inf
- x के लिए 1 से 2m की सीमा में
- op :=min of op, हल करें(arr, i + x, max of x and m, dp)
- dp[i, m] :=arr[i] - op
- रिटर्न डीपी[i, m]
- वास्तविक विधि इस प्रकार होगी -
- n :=पाइल्स ऐरे का आकार, एक ऐरे बनाएं जिसे arr साइज n कहा जाता है
- arr[n - 1] :=बवासीर[n - 1]
- i के लिए :=n – 2 डाउन टू 0
- arr[i] :=arr[i + 1] + बवासीर[i]
- आकार का एक मैट्रिक्स बनाएं (n + 1) x (n + 1) और इसे -1 से भरें
- रिटर्न सॉल्व (गिरफ्तारी, 0, 1, डीपी)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void printVector(vector <int> v){
for(int i =0;i<v.size();i++)cout << v[i] << " ";
cout << endl;
}
int stoneGameII(vector<int>& piles) {
int n = piles.size();
vector <int> arr(n);
arr[n-1] = piles[n-1];
for(int i = n-2;i>=0;i--)arr[i] = arr[i+1] + piles[i];
vector < vector <int> > dp(n+1,vector <int> (n+1,-1));
return solve(arr,0,1,dp);
}
int solve(vector <int> arr, int i, int m, vector < vector <int> > &dp){
if(i >=arr.size())return 0;
if(dp[i][m]!=-1)return dp[i][m];
if(i-1+2*m >=arr.size())return arr[i];
int opponentCanTake = INT_MAX;
for(int x =1;x<=2*m;x++){
opponentCanTake = min(opponentCanTake,solve(arr,i+x,max(x,m),dp));
}
dp[i][m] = arr[i] - opponentCanTake;
return dp[i][m];
}
};
main(){
vector<int> v = {2,7,9,4,4};
Solution ob;
cout <<(ob.stoneGameII(v));
} इनपुट
[2,7,9,4,4]
आउटपुट
10