জিতাবার কে ভবিষ্যদ্বাণী করা C++-এ

সমস্যা বিবরণ

নন-নেগেটিভ ইন্টিজারের একটি অ্যারে আছে। دوজন খেলাড়ি বاری বاری থেকে অ্যারের দুটি প্রান্ত থেকে একটি সংখ্যা নেয়। সব সংখ্যা নেওয়া শেষে যের স্কোর বেশি সে জিতবে। প্রথম খেলাড়ি জিতে পারে কিনা তা বের করতে হবে (উভয়ই অপ্টিমালি খেলে)।

উদাহরণ

ইনপুট: [1, 5, 233, 7]

প্রথম খেলাড়ি ১ নেয়। দ্বিতীয় খেলাড়ি ৫ বা ৭ নিতে পারে। যেটাও নেয়, প্রথম খেলাড়ি ২৩৩ নেবে। প্রথম খেলাড়ির টোটাল = ২৩৪, দ্বিতীয় = ১২। প্রথম খেলাড়ি জিতবে → true।

অ্যালগরিদম: ডাইনামিক প্রোগ্রামিং

player1[i][j] = সাবঅ্যারে i..j থেকে প্রথম খেলাড়ি যেটা পেতে পারে।
player2[i][j] = সাবঅ্যারে i..j থেকে দ্বিতীয় খেলাড়ি যেটা পেতে পারে।
sum[i][j] = সাবঅ্যারে i..j এর যোগফল।

রিকারেন্স:

• player1[i][j] = max(arr[i] + player2[i+1][j], arr[j] + player2[i][j-1])
• player2[i][j] = sum[i][j] - player1[i][j]

বেস কেস: i == j হলে player1[i][i] = arr[i]।

সাবপ্রব্লেম দৈর্ঘ্য ১ থেকে n পর্যন্ত সমাধান করুন।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return true;

        vector<vector<lli>> player1(n, vector<lli>(n));
        vector<vector<lli>> player2(n, vector<lli>(n));
        vector<vector<lli>> sum(n, vector<lli>(n));

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) sum[i][j] = nums[i];
                else sum[i][j] = nums[j] + sum[i][j-1];
            }
        }

        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (i + 1 <= j) {
                    lli pickLeft = nums[i] + (player2[i+1][j] == -1 ? 0 : player2[i+1][j]);
                    lli pickRight = nums[j] + (player2[i][j-1] == -1 ? 0 : player2[i][j-1]);
                    player1[i][j] = max(pickLeft, pickRight);
                } else {
                    player1[i][j] = nums[i];
                }
                player2[i][j] = sum[i][j] - player1[i][j];
            }
        }
        return player1[0][n-1] >= player2[0][n-1];
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 5, 233, 7};
    cout << ob.PredictTheWinner(v); // আউটপুট: 1 (true)
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n²) — ডিপি টেবিল ফিল আপ।
• স্থান জটিলতা: O(n²) — তিনটি n×n ম্যাট্রিক্স।