मान लीजिए दो व्यक्ति एलिस और बॉब हैं, वे पत्थरों के ढेर के साथ अपना खेल जारी रखते हैं। कई ढेर एक पंक्ति में रखे गए हैं, और प्रत्येक ढेर में piles[i] सरणी में एक सकारात्मक पूर्णांक संख्या में पत्थर हैं। खेल का उद्देश्य सबसे अधिक पत्थरों के साथ समाप्त करना है। एलिस और बॉब बारी-बारी से खेलते हैं, एलिस पहले शुरू करती है। प्रारंभ में, M = 1। प्रत्येक खिलाड़ी की बारी पर, वह खिलाड़ी पहले X शेष ढेरों के सभी पत्थर ले सकता है, जहां 1 <= X <= 2M। फिर, हम M = max(M, X) सेट करते हैं। खेल तब समाप्त होता है जब कोई पत्थर नहीं बचते। उदाहरण के लिए, यदि piles = [2,7,9,4,4], तो आउटपुट 10 होगा। ऐसा इसलिए है क्योंकि यदि एलिस शुरू में एक ढेर लेती है, तो बॉब दो ढेर लेता है, फिर एलिस फिर से 2 ढेर लेती है। एलिस को कुल 2 + 4 + 4 = 10 ढेर मिलते हैं। यदि एलिस शुरू में दो ढेर लेती है, तो बॉब बचे हुए तीनों ढेर ले सकता है। इस मामले में, एलिस को 2 + 7 = 9 ढेर मिलते हैं। इसलिए हम 10 वापस करेंगे क्योंकि यह बड़ा है।
हल करने के चरण
- solve नामक एक पुनरावर्ती फ़ंक्शन बनाएं, जो सरणी, i, m और dp मैट्रिक्स लेता है
- यदि i >= सरणी का आकार, तो 0 वापस करें
- यदि dp[i][m] != -1, तो dp[i][m] वापस करें
- यदि i-1 + 2m >= सरणी का आकार, तो arr[i] वापस करें
- op := अनंत
- x को 1 से 2m तक लूप करें
- op := min(op, solve(arr, i+x, max(x,m), dp))
- dp[i][m] := arr[i] - op
- dp[i][m] वापस करें
- वास्तविक विधि:
- n := piles सरणी का आकार, आकार n की एक सरणी arr बनाएं
- arr[n-1] := piles[n-1]
- i := n-2 से 0 तक नीचे जाएं
- arr[i] := arr[i+1] + piles[i]
- (n+1) x (n+1) आकार की एक मैट्रिक्स बनाएं और इसे -1 से भरें
- solve(arr, 0, 1, dp) वापस करें
उदाहरण
#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
