Trò chơi đá II trong C++

Alice và Bob chơi game lấy đá từ hàng cột. Mỗi lượt lấy X cột đầu (1 <= X <= 2M), sau đó cập nhật M = max(M, X). Alice đi trước. Tối đa hóa số đá Alice có được.

Ví dụ: piles = [2,7,9,4,4] → Alice lấy 1, Bob lấy 2, Alice lấy 2 → Alice = 2+4+4 = 10.

Thuật toán giải quyết (DP đệ quy + Suffix Sum)

1. Tính mảng hậu tố arr[i] = tổng đá từ i đến cuối.
2. Hàm solve(arr, i, m) = tối đa đá người chơi hiện tại có được từ vị trí i với tham số m.
3. Cơ sở: nếu i >= n → 0; nếu i-1+2*m >= n → lấy hết arr[i].
4. Đệ quy: thử mọi x = 1..2m, đối thủ sẽ chơi tối ưu → người chơi hiện tại nhận arr[i] - min_opponent.
5. Memoization dp[i][m].

Ví dụ minh họa (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() {
    vector<int> v = {2, 7, 9, 4, 4};
    Solution ob;
    cout << ob.stoneGameII(v);
}

Đầu vào

[2,7,9,4,4]

Đầu ra

10