Stone Game ใน C++

คำอธิบายปัญหา

Alex และ Lee เล่นเกมหิน กองหินจำนวนคู่เรียงเป็นแถว แต่ละกองมีหิน piles[i] สลับกันหยิบกองแรกหรือกองสุดท้าย เล่นอย่างเหมาะสมที่สุด Alex เริ่มก่อน ต้องการทราบว่า Alex ชนะได้หรือไม่

ตัวอย่าง: [5,3,4,5] → true (Alex หยิบ 5 แรก แล้วชนะได้)

ข้อสังเกตสำคัญ

เนื่องจากจำนวนกองเป็นคู่ และทั้งคู่เล่น optimal → Alex ชนะเสมอ (สามารถบังคับให้ได้ผลรวมกองคี่หรือกองคู่ที่มากกว่า)

แต่โจทย์ขอให้ implement DP แบบเต็มๆ

วิธีแก้ปัญหา (DP Interval)

dp[i][j] = คะแนนสูงสุดที่ผู้เล่นคนปัจจุบันได้มากกว่าคู่แข่ง ในช่วง i..j
dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
ฐาน: dp[i][i] = piles[i]
Alex ชนะถ้า dp[0][n-1] > 0

ตัวอย่างโค้ด 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, 0));
        
        for(int i = 0; i < n; i++) dp[i][i] = piles[i];
        
        for(int len = 2; len <= n; len++) {
            for(int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
            }
        }
        return dp[0][n-1] > 0;
    }
};

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

อินพุต