C++ में स्टोन गेम (Stone Game)

मान लीजिए दो खिलाड़ी एलेक्स और ली पत्थरों के ढेर के साथ एक खेल खेलते हैं। ढेर की संख्या सम है जो एक पंक्ति में व्यवस्थित हैं, और प्रत्येक ढेर में कुछ पत्थर piles[i] हैं। खेल का उद्देश्य सबसे अधिक पत्थरों के साथ समाप्त होना है। जब कुल पत्थरों की संख्या विषम होती है, तो कोई टाई नहीं होती। एलेक्स और ली बारी-बारी से खेलते हैं, एलेक्स पहले शुरू करता है। प्रत्येक चाल में, एक खिलाड़ी पंक्ति के शुरुआत या अंत से पत्थरों का पूरा ढेर लेता है। यह तब तक चलता है जब तक कोई ढेर नहीं बचता, जिस बिंदु पर सबसे अधिक पत्थरों वाला व्यक्ति जीतता है। मान लें कि एलेक्स और ली इष्टतम रूप से खेलते हैं, जांचें कि क्या एलेक्स खेल जीतता है या नहीं।

उदाहरण के लिए, यदि इनपुट [5,3,4,5] है, तो परिणाम true होगा।

समाधान दृष्टिकोण

1. n := piles का आकार

2. dp मैट्रिक्स n×n और प्रीफिक्स सम ऐरे pre बनाएं

3. pre[i+1] = pre[i] + piles[i] से प्रीफिक्स सम भरें

4. लंबाई l = 2 से n तक: सभी i,j के लिए dp[i][j] की गणना करें

5. 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])

6. dp[0][n-1] > dp[0][n-1] - pre[n] जांचकर true/false लौटाएं

C++ कार्यान्वयन

#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]; 
    } 
}; 

int main(){ 
    vector<int> v = {5,3,4,5}; 
    Solution ob; 
    cout << (ob.stoneGame(v)); 
    return 0; 
}

इनपुट

[5,3,4,5]

आउटपुट

1