Medium
Related Topics: Array / Math / Dynamic Programming / Prefix Sum / Game Theory
LeetCode Source

解題想法

首先，我們需要建立一個二維 DP 陣列 dp，其中 dp[i][j] 代表當有 i 堆石頭剩下，並且在 j 場比賽中，先手能夠獲得的最大石頭數量。

為了處理每個狀態，我們會考慮先手在每個回合中取走的石頭數量，並計算對手能夠獲得的最優解。

狀態轉移過程中，我們使用 total 來記錄剩餘石頭的總數，並更新 dp 陣列。

初始化部分包括計算每個位置的後綴和，以便快速獲取剩餘石頭的總數。

最終結果存儲在 dp[0][1] 中，其中 0 代表從第一堆石頭開始，1 代表遊戲的第一場比賽。

Complexity

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Python

def stoneGameII(piles):
    n = len(piles)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    suffix_sum = [0] * (n + 1)
    
    # 預計算每個位置的後綴和
    for i in range(n - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + piles[i]
    
    # 動態規劃
    def dfs(i, M):
        if i == n:
            return 0
        if dp[i][M] != 0:
            return dp[i][M]
        max_score = float('-inf')
        total = 0
        for x in range(1, 2 * M + 1):
            if i + x > n:
                break
            total += piles[i + x - 1]
            max_score = max(max_score, total - dfs(i + x, max(M, x)))
        dp[i][M] = max_score
        return max_score
    
    return (suffix_sum[0] + dfs(0, 1)) // 2

C++

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector<int> suffix_sum(n + 1, 0);
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

        // 計算每個位置的後綴和
        for (int i = n - 1; i >= 0; --i) {
            suffix_sum[i] = suffix_sum[i + 1] + piles[i];
        }

        function<int(int, int)> dfs = [&](int i, int M) {
            if (i == n) return 0;
            if (dp[i][M] != 0) return dp[i][M];
            int max_score = INT_MIN;
            int total = 0;
            for (int x = 1; x <= 2 * M; ++x) {
                if (i + x > n) break;
                total += piles[i + x - 1];
                max_score = max(max_score, total - dfs(i + x, max(M, x)));
            }
            return dp[i][M] = max_score;
        };

        return (suffix_sum[0] + dfs(0, 1)) / 2;
    }
};