LeetCode 解題筆記：877. Stone Game

作者：王一哲
日期：2026年8月2日


LeetCode 題目連結：877. Stone Game

解題想法

中等難度題。這題看起來與昨天的 486. Predict the Winner 幾乎一樣，題目給一個陣列 $piless$，兩個玩家 Alice、Bob 每次行動時可以從 $piles$ 兩端選取並移除一堆石頭，Alice 先行動，如果 Alice 拿到比較多的石頭回傳 True。這題一 樣可以用動態規畫解題，建立一個 $n \times n$ 的二維陣列 $dp[i][j]$ 代表可選的值剩下 $piles[i]$ ~ $piles[j]$ 時目前行動玩家與另一人的最大分差。更新狀態時有 2 種選擇：

1. 行動1，選 $piles[i]$，新的區間為 $piles[i+1]$ ~ $piles[j]$，最大分差為 $piles[i] - dp[i+1][j]$
2. 行動2，選 $piles[j]$，新的區間為 $piles[i] ~ piles[j-1]$，最大分差為 $piles[j] - dp[i][j-1]$

玩家採用最佳策略，從行動1、2之中選分數高的，因此 $$ dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]) $$ 當 $i = j$ 時，只能選擇一個數字，$dp[i][j] = piles[i]$。更新 $dp$ 時，要從長度 $2$ 開始，直到長度等於 $n$ 為止，因為長度較長的狀態，是基於長度較短的狀態更新數值。更新完畢之後，如果 $dp[0][n-1] \geq 0$，Alice 獲勝，回傳 True。

但是這題多加了兩個條件：$piles$ 的長度為偶數，$piles$ 所有的數量加起來為奇數，答案一定是 True。因為 Alice 可以選擇取走所有奇數索引值或是偶數索引值的石頭堆，選擇總數多的石頭堆就能獲勝。

Python 程式碼

dp. Runtime: 127 ms, beats 41.69%. Memory: 25.47 MB, beats 34.68%.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)  # 長度
        # dp[i][j] 範圍為 piles[i] ~ piles[j] 對應的最大分差
        dp = [[0]*n for _ in range(n)]
        # 初始化，只剩下一堆能選
        for i in range(n):
            dp[i][i] = piles[i]
        # 更新 dp，外層更新長度 2 ~ n，內層更新起點 i = 0 ~ n - len
        for length in range(2, n+1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        # 如果 dp[0][n-1] > 0，Alice 獲勝，回傳 True
        return dp[0][n-1] > 0

Runtime: 0 ms, beats 100.00%. Memory: 19.33 MB, beats 55.87%.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True

C++ 程式碼

dp. Runtime: 5 ms, beats 36.29%. Memory: 19.61 MB, beats 20.88%.

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = (int)piles.size();  // 長度
        // dp[i][j] 範圍為 piles[i] ~ piles[j] 對應的最大分差
        vector<vector<int>> dp (n, vector<int> (n, 0));
        // 初始化，只剩下一堆能選
        for(int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }
        // 更新 dp，外層更新長度 2 ~ n，內層更新起點 i = 0 ~ n - len
        for(int length = 2; length <= n; length++) {
            for(int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
            }
        }
        // 如果 dp[0][n-1] > 0，Alice 獲勝，回傳 True
        return dp[0][n-1] > 0;
    }
};

Runtime: 0 ms, beats 100.00%. Memory: 10.34 MB, beats 87.75%.

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};

C 語言程式碼

dp. Runtime: 3 ms, beats 1.99%. Memory: 9.52 MB, beats 1.32%.

bool stoneGame(int* piles, int pilesSize) {
    // dp[i][j] 範圍為 piles[i] ~ piles[j] 對應的最大分差
    int dp[510][510];
    memset(dp, 0, sizeof(dp));
    // 初始化，只剩下一堆能選
    for(int i = 0; i < pilesSize; i++) {
        dp[i][i] = piles[i];
    }
    // 更新 dp，外層更新長度 2 ~ n，內層更新起點 i = 0 ~ pilesSize - len
    for(int length = 2; length <= pilesSize; length++) {
        for(int i = 0; i <= pilesSize - length; i++) {
            int j = i + length - 1;
            int left = piles[i] - dp[i+1][j];                
            int right = piles[j] - dp[i][j-1];
            if (left > right) dp[i][j] = left;
            else dp[i][j] = right;
        }
    }
    // 如果 dp[0][pilesSize-1] > 0，Alice 獲勝，回傳 True
    return dp[0][pilesSize-1] > 0;
}

Runtime: 0 ms, beats 100.00%. Memory: 8.66 MB, beats 56.95%.

bool stoneGame(int* piles, int pilesSize) {
    return true;
}