Predict the Winner – ทายผู้ชนะเกมเลือกตัวเลขใน C++

ปัญหา: Predict the Winner

มีอาร์เรย์คะแนน (non-negative integers) ผู้เล่น 2 คน สลับกันเลือกตัวเลขจาก ปลายซ้ายหรือปลายขวา ของอาร์เรย์ จนกว่าจะหมด ผู้ที่ได้คะแนนรวมมากกว่า ชนะ ทายว่าผู้เล่นคนแรกชนะได้หรือไม่ (สมมติทั้งคู่เล่น optimal)

ตัวอย่าง

[1, 5, 233, 7]

• P1 เลือก 1 (ซ้าย) → เหลือ [5, 233, 7]
• P2 เลือก 5 หรือ 7 → สมมติเลือก 7 → เหลือ [5, 233]
• P1 เลือก 233 → รวม P1 = 234, P2 = 12 → P1 ชนะ

Output: true

แนวทางแก้ปัญหา: Dynamic Programming

State Definition

dp[i][j] = คะแนนสูงสุดที่ผู้เล่นปัจจุบันได้จาก subarray nums[i..j]

Recurrence

ผู้เล่นปัจจุบันเลือกซ้ายหรือขวา:

• เลือกซ้าย: nums[i] + (sum(i+1,j) - dp[i+1][j])
• เลือกขวา: nums[j] + (sum(i,j-1) - dp[i][j-1])

โดย sum(i,j) = ผลรวม subarray i..j

→ dp[i][j] = max(nums[i] + sum(i+1,j) - dp[i+1][j], nums[j] + sum(i,j-1) - dp[i][j-1])

ลดรูป: dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) + sum(i,j) - sum(i,j) → จริงๆ แล้ว:

dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) (เก็บความต่างคะแนน)

Base Case

dp[i][i] = nums[i]

คำตอบสุดท้าย

ผู้เล่น 1 ชนะถ้า dp[0][n-1] >= 0 (คะแนนมากกว่าหรือเท่าคู่แข่ง)

ตัวอย่างโค้ด C++ (Space Optimized)

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

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp = nums; // dp[i] = ความต่างคะแนน max สำหรับ subarray เริ่มที่ i ความยาวปัจจุบัน

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i] = max(nums[i] - dp[i+1], nums[j] - dp[i]);
            }
        }
        return dp[0] >= 0;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 5, 233, 7};
    cout << (ob.PredictTheWinner(v) ? "true" : "false"); // true
    return 0;
}

โค้ดต้นฉบับ (2D DP พร้อม sum array)

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

        vector<vector<long long>> dp(n, vector<long long>(n));
        vector<vector<long long>> sum(n, vector<long long>(n));

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

        for (int i = 0; i < n; i++) dp[i][i] = nums[i];

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = max(nums[i] + (sum[i+1][j] - dp[i+1][j]),
                               nums[j] + (sum[i][j-1] - dp[i][j-1]));
            }
        }
        return dp[0][n-1] >= sum[0][n-1] - dp[0][n-1];
    }
};

ความซับซ้อน

ข้อสังเกต

• เกมนี้เป็น "Zero-sum game" – คะแนนรวมคงที่ การเพิ่มคะแนนตัวเอง = การลดคะแนนคู่แข่ง
• DP 1D ทำได้เพราะ dp[i][j] ขึ้นกับ dp[i+1][j] และ dp[i][j-1] เท่านั้น
• LeetCode 486 – ปัญหา Game Theory คลาสสิก