Stone Game II ใน C++: เกมกองหิน Alice vs Bob เล่นเหมาะสมที่สุด

โจทย์

อาร์เรย์ piles แทนกองหิน Alice เริ่มก่อน M=1 แต่ละรอบผู้เล่นหยิบ X กองแรก (1 ≤ X ≤ 2M) ตั้ง M = max(M, X) ใครได้หินมากที่สุดชนะ หาจำนวนหินสูงสุดที่ Alice ได้

ตัวอย่าง: [2,7,9,4,4] → 10 (Alice หยิบ 1, Bob หยิบ 2, Alice หยิบ 2 → 2+4+4=10)

แนวคิด: DP + Minimax (Suffix Sum)

ให้ arr[i] = suffix sum จาก i ถึงสุด (หินที่เหลือทั้งหมด)
solve(i, M) = หินสูงสุดที่ผู้เล่นคนปัจจุบันได้จากตำแหน่ง i ด้วย M นี้
คู่แข่งจะเล่นเพื่อลดค่าของเรา → เราได้ arr[i] - min(opponent)

ขั้นตอน

1. คำนวณ suffix sum arr: arr[n-1]=piles[n-1], arr[i]=arr[i+1]+piles[i]
2. DP memo: dp[i][m] = -1 เริ่มต้น
3. solve(i, m):
   • ถ้า i >= n → 0
   • ถ้า dp[i][m] != -1 → return
   • ถ้า i-1+2*m >= n → หยิบหมดได้ → return arr[i]
   • opponent = INF
   • ลูป x = 1 ถึง 2*m: opponent = min(opponent, solve(i+x, max(x,m)))
   • dp[i][m] = arr[i] - opponent
4. คืน solve(0, 1)

ตัวอย่างโค้ด C++

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

class Solution {
    int solve(vector<int>& arr, int i, int m, vector<vector<int>>& dp) {
        if (i >= arr.size()) return 0;
        if (dp[i][m] != -1) return dp[i][m];
        if (i - 1 + 2 * m >= arr.size()) return arr[i];
        
        int opponent = INT_MAX;
        for (int x = 1; x <= 2 * m; x++) {
            opponent = min(opponent, solve(arr, i + x, max(x, m), dp));
        }
        return dp[i][m] = arr[i] - opponent;
    }
    
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector<int> arr(n);
        arr[n-1] = piles[n-1];
        for (int i = n-2; i >= 0; i--) arr[i] = arr[i+1] + piles[i];
        
        vector<vector<int>> dp(n+1, vector<int>(n+1, -1));
        return solve(arr, 0, 1, dp);
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,7,9,4,4};
    cout << ob.stoneGameII(v); // 10
    return 0;
}

อินพุต / เอาต์พุต

Input: [2,7,9,4,4]

Output: 10

ความซับซ้อน

• Time: O(n³) - state n×n แต่ละลูป 2m ≤ 2n
• Space: O(n²)