ধরুন এলিস এবং বব নামে দুজন ব্যক্তি আছেন, তারা পাথরের স্তূপ নিয়ে তাদের খেলা চালিয়ে যাচ্ছেন। একটি সারিতে বেশ কয়েকটি পাইল স্থাপন করা হয়েছে, এবং প্রতিটি স্তূপে একটি অ্যারের পাইলগুলিতে পাথরের একটি ধনাত্মক পূর্ণসংখ্যা রয়েছে[i]। আমাদের খেলার উদ্দেশ্য হল সর্বাধিক পাথর দিয়ে শেষ করা। এলিস এবং বব মোড় নেয়, এলিস প্রথমে শুরু করে। প্রাথমিকভাবে, M =1. প্রতিটি খেলোয়াড়ের পালাক্রমে, সেই খেলোয়াড় প্রথম X অবশিষ্ট পাইলের সমস্ত পাথর নিতে পারে, এখানে 1 <=X <=2M। তারপর, আমরা M =max(M, X) সেট করি। খেলা শেষ হয় যখন কোন পাথর বাকি থাকে না। তাই যদি পাইলস =[2,7,9,4,4], তাহলে আউটপুট হবে 10। এর কারণ হল অ্যালিস যদি শুরুতে একটি পাইল নেয়, তাহলে বব দুটি পাইল নেয়, তারপর এলিস আবার 2টি পাইল নেয়। এলিস তার হাতে 2 + 4 + 4 =10 মোট পাইলস পেতে পারে। অ্যালিস যদি শুরুতে দুটি পাইল নেয়, তাহলে বব বাকি তিনটি পাইলই নিতে পারে। এই ক্ষেত্রে, এলিস 2 + 7 =9 পাইলস পান। তাই আমরা 10 রিটার্ন পাব যেহেতু এটি বড়।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- সলভ নামে একটি পুনরাবৃত্ত ফাংশন তৈরি করুন, যেটি অ্যারে, i, m এবং dp নামক একটি ম্যাট্রিক্স নেবে।
- যদি i>=আকারের arr, তাহলে 0 ফেরত দিন
- যদি dp[i, m] -1 না হয়, তাহলে dp[i, m] ফেরত দিন
- যদি i – 1 + 2m>=অ্যারের আকার, তারপর arr[i] ফেরত দিন
- op :=inf
- এক্সের জন্য 1 থেকে 2m পরিসরে
- op :=op এর মিনিট, সমাধান(arr, i + x, x এর সর্বোচ্চ এবং m, dp)
- dp[i, m] :=arr[i] – op
- রিটার্ন dp[i, m]
- প্রকৃত পদ্ধতি হবে − এর মত
- n :=পাইলস অ্যারের আকার, একটি অ্যারে তৈরি করুন যাকে বলা হয় অ্যারের আকার n
- arr[n - 1] :=পাইলস[n – 1]
- এর জন্য i :=n – 2 নিচে 0
- arr[i] :=arr[i + 1] + পাইলস[i]
- আকারের একটি ম্যাট্রিক্স তৈরি করুন (n + 1) x (n + 1) এবং এটি -1 দিয়ে পূরণ করুন
- রিটার্ন সলভ(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
