মান লেযিয়ে অ্যালেক্স এবং লি নামক দুটি খেলোয়াড় পাথরের কুড়া দিয়ে খেলছে। জোড় সংখ্যক কুড়া সারিতে সাজানো আছে, প্রতিটি কুড়ায় কিছু পাথর piles[i] আছে। লক্ষ্য হল সবচেয়ে বেশি পাথর দিয়ে শেষ করা। মোট পাথর বিজোড় হলে টাই নেই। অ্যালেক্স প্রথমে শুরু করে। প্রতিটি চুলে একজন খেলোয়াড় সারির যেকোনো একটি প্রান্ত থেকে পুরো কুড়াটি নেয়। কুড়া না থাকা পর্যন্ত চলে, সবচেয়ে বেশি পাথর যার থাকে সে জিতবে। অ্যালেক্স এবং লি অপ্টিমালি খেললে অ্যালেক্স জিতবে কিনা যাচাই করতে হবে। ইনপুট [5,3,4,5] হলে true। অ্যালেক্স প্রথমে ৫ নিলে (শুরু বা শেষ), সারি [3,4,5]। লি ৩ নিলে সারি [4,5], অ্যালেক্স ৫ নিয়ে ১০ পয়েন্টে জিতে। লি শেষ ৫ নিলে সারি [3,4], অ্যালেক্স ৪ নিয়ে ৯ পয়েন্টে জিতে। তাই প্রথম ৫ নেওয়া জয়ের মুভ ছিল।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
n := piles.size()
n x n আকারের dp ম্যাট্রিক্স এবং n+1 আকারের pre অ্যারে তৈরি করুন
i = 0 থেকে n-1 পর্যন্ত: pre[i+1] := pre[i] + piles[i]
l = 2 থেকে n পর্যন্ত লুপ চালান
i := 0, j := l-1; j < n হলে i++, j++
dp[i][j] := max(piles[j] + pre[j] - pre[i] - dp[i][j-1], piles[i] + pre[i+2] - pre[j] + dp[i+1][j])
যদি dp[0][n-1] > dp[0][n-1] - pre[n] হয় true রিটার্ন করুন
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: bool stoneGame(vector<int>& piles) { int n = piles.size(); vector < vector <int> > dp(n,vector <int>(n)); vector <int> pre(n + 1); for(int i = 0; i < n; i++){ pre[i + 1] = pre[i] + piles[i]; } for(int l = 2; l <= n; l++){ for(int i = 0, j = l - 1; j < n; i++, j++){ dp[i][j] = max(piles[j] + pre[j] - pre[i] - dp[i][j - 1], piles[i] + pre[i + 2] - pre[j] + dp[i + 1][j]); } } return dp[0][n - 1] > dp[0][n - 1] - pre[n]; } }; main(){ vector<int> v = {5,3,4,5}; Solution ob; cout << (ob.stoneGame(v)); }ইনপুট
[5,3,4,5]
আউটপুট
1
