877. Stone Game

題目 / Problem

中文： Alice 和 Bob 玩一個取石子遊戲。有 偶數 堆石子排成一列，每堆有 piles[i] 顆石子（正整數）。所有石子的 總數是奇數，所以不會平手。兩人輪流取，Alice 先手。每一回合，玩家只能從這一列的 最左端 或 最右端 拿走整堆石子。當沒有石子時，拿到石子最多的人獲勝。假設兩人都採取 最佳策略，若 Alice 會贏就回傳 true，否則回傳 false。

English: Alice and Bob play a stone-taking game. There is an even number of piles in a row; each pile has piles[i] stones (a positive integer). The total number of stones is odd, so there are no ties. They alternate turns with Alice going first. On each turn a player removes the entire pile from either the left end or the right end of the row. When no piles remain, whoever holds the most stones wins. Assuming both play optimally, return true if Alice wins, else false.

Constraints / 限制： - 2 <= piles.length <= 500，且長度為偶數 / length is even - 1 <= piles[i] <= 500 - sum(piles[i]) 是奇數 / is odd

Example / 範例： piles = [5,3,4,5] → true。Alice 先拿最左的 5，之後不論 Bob 怎麼拿，Alice 都能贏。

名詞解釋 / Glossary

• 動態規劃 / Dynamic Programming (DP)： 把大問題拆成重疊的小問題，先解小問題並把答案存起來，避免重複計算。A technique that breaks a big problem into overlapping subproblems, solving each once and storing the result.
• 區間 / Interval [i..j]： 指陣列中從索引 i 到 j 這一段連續的石子堆。A contiguous slice of the array from index i to j — exactly the piles still on the board at some point.
• 淨分差 / Score difference： 我們不分開記錄兩人的分數，而是記錄「當前該行動的人能領先對手多少分」。Instead of tracking two scores, we track how many points the player-to-move can lead the opponent by.
• 博弈論 / Game theory (minimax)： 雙方都最佳化：輪到你時你選對自己最有利的一步，因此對手拿到的也是「對手最佳化後」的結果。Both sides play optimally; you pick the move that maximizes your outcome, knowing the opponent will do the same on their turn.
• 二維陣列 / 2D array： 一個用兩個索引 dp[i][j] 存取的表格，這裡代表區間 [i..j] 的答案。A table indexed by two numbers dp[i][j], here holding the answer for interval [i..j].

思路

先講最直覺的暴力解：在每一回合，當前玩家可以拿最左或最右，我們對兩種選擇各遞迴往下算，模擬整棵決策樹。問題是每堆各有兩種拿法，樹會指數級爆炸（約 2^n），n 到 500 完全跑不動。關鍵觀察是：遊戲的「狀態」其實只由 剩下哪一段連續區間 [i..j] 決定 —— 因為每次只從兩端拿，剩下的一定是一段連續的堆。這代表很多分支會落到相同的區間，出現大量重疊子問題，正是動態規劃的訊號。接著是一個化簡技巧：與其分別記 Alice、Bob 的分數，不如定義 dp[i][j] 為「輪到某人面對區間 [i..j] 時，他能比對手多拿的淨分差」。當前玩家有兩種選擇：拿左端 piles[i]，之後對手面對 [i+1..j]，對手也會最佳化，所以自己的淨領先是 piles[i] - dp[i+1][j]（減號是因為對手的領先就是我的落後）；或拿右端 piles[j]，得到 piles[j] - dp[i][j-1]。取兩者較大值即可。基底是單堆 dp[i][i] = piles[i]。最後 dp[0][n-1] > 0 就代表先手 Alice 淨領先，回傳 true。（有趣的是：本題因為堆數偶數、總和奇數，Alice 其實永遠能贏，直接 return true 也對；但下面用 DP 是為了學會通用解法。）

Start with the brute force: on each turn the current player can take from the left or the right, so we recurse into both choices and simulate the whole decision tree. That tree branches two ways per pile, blowing up to about 2^n — hopeless for n up to 500. The key observation is that a game state is fully described by which contiguous interval [i..j] remains, because you only ever remove from the two ends. Many different branches collapse onto the same interval, so subproblems overlap heavily — the classic signal for dynamic programming. Then a simplifying trick: rather than tracking Alice's and Bob's scores separately, define dp[i][j] as the net lead the player-to-move can secure over the opponent on interval [i..j]. That player has two options: take the left pile piles[i], after which the opponent faces [i+1..j] and plays optimally, so my net lead is piles[i] - dp[i+1][j] (we subtract because the opponent's lead is my deficit); or take the right pile for piles[j] - dp[i][j-1]. Pick the larger. The base case is a single pile, dp[i][i] = piles[i]. Finally, dp[0][n-1] > 0 means first-mover Alice ends ahead, so we return true. (Fun fact: with an even number of piles and an odd total, Alice can always win, so return true alone is correct — but we build the DP to learn the general method.)

逐步走查 / Walkthrough

以 piles = [5,3,4,5]，n = 4 為例。我們用一個 4×4 的表 dp，dp[i][j] = 面對區間 [i..j] 的玩家能領先的淨分差。先填長度 1 的區間（對角線），再填長度 2、3、4。

Base case / 基底（長度 1）：

長度 2 / length 2： 公式 dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])

• dp[0][1] = max(5 − dp[1][1], 3 − dp[0][0]) = max(5−3, 3−5) = max(2, −2) = 2
• dp[1][2] = max(3 − dp[2][2], 4 − dp[1][1]) = max(3−4, 4−3) = max(−1, 1) = 1
• dp[2][3] = max(4 − dp[3][3], 5 − dp[2][2]) = max(4−5, 5−4) = max(−1, 1) = 1

長度 3 / length 3：

• dp[0][2] = max(5 − dp[1][2], 4 − dp[0][1]) = max(5−1, 4−2) = max(4, 2) = 4
• dp[1][3] = max(3 − dp[2][3], 5 − dp[1][2]) = max(3−1, 5−1) = max(2, 4) = 4

長度 4 / length 4（整個陣列）：

• dp[0][3] = max(piles[0] − dp[1][3], piles[3] − dp[0][2]) = max(5 − 4, 5 − 4) = max(1, 1) = 1

dp[0][3] = 1 > 0，代表 Alice 最終能領先 1 分 → 回傳 true。對照範例，Alice 拿第一個 5，最後以 10 比 7 之類的比分獲勝。/ dp[0][3] = 1 > 0, so Alice ends 1 point ahead → return true.

Solution — C

// 演算法：區間 DP。dp[i][j] = 面對區間 [i..j] 的玩家能領先對手的淨分差。
// Algorithm: interval DP. dp[i][j] = net lead the player-to-move can get on piles[i..j].
// 轉移：拿左端得 piles[i]-dp[i+1][j]，拿右端得 piles[j]-dp[i][j-1]，取大者。
// Transition: take left -> piles[i]-dp[i+1][j], take right -> piles[j]-dp[i][j-1]; keep the max.
// 最後 dp[0][n-1] > 0 表示先手 Alice 淨領先 / final dp[0][n-1] > 0 means Alice leads.

#include <stdbool.h>   // 提供 bool / true / false / gives us bool, true, false
#include <stdlib.h>    // 提供 malloc 和 free / gives us malloc and free

bool stoneGame(int* piles, int pilesSize) {
    int n = pilesSize;                       // n 是石子堆數 / n = number of piles

    // 配置一個 n×n 的二維表。C 沒有內建二維陣列，我們用「指標的陣列」。
    // Allocate an n×n table. C has no built-in 2D array, so we use an array of pointers.
    int** dp = (int**)malloc(n * sizeof(int*));   // dp 是 n 個「int 指標」/ dp holds n int-pointers (rows)
    for (int i = 0; i < n; i++) {
        // calloc 配置一列 n 個 int 並全部初始化為 0 / calloc gives n ints, all zeroed
        dp[i] = (int*)calloc(n, sizeof(int));
    }

    // 基底：只剩一堆時，該玩家就拿走它，淨領先等於這堆的石子數。
    // Base case: with one pile left, the player takes it; net lead = that pile's stones.
    for (int i = 0; i < n; i++) {
        dp[i][i] = piles[i];                 // 對角線填入單堆的值 / fill the diagonal
    }

    // 依「區間長度」由小到大填表。len 從 2 開始，因為長度 1 已填好。
    // Fill by increasing interval length. Start at 2 since length 1 is done.
    for (int len = 2; len <= n; len++) {
        // i 是區間左端；j = i+len-1 是右端，不能超出陣列。
        // i is the left end; j = i+len-1 is the right end, must stay in bounds.
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;             // 由左端和長度算出右端 / right end from left + length

            int takeLeft  = piles[i] - dp[i + 1][j];  // 拿左端後對手面對 [i+1..j] / after taking left, opponent faces [i+1..j]
            int takeRight = piles[j] - dp[i][j - 1];  // 拿右端後對手面對 [i..j-1] / after taking right, opponent faces [i..j-1]

            // 當前玩家選對自己較有利（淨領先較大）的那一步。
            // The current player picks whichever move gives the larger net lead.
            dp[i][j] = takeLeft > takeRight ? takeLeft : takeRight;
        }
    }

    bool aliceWins = dp[0][n - 1] > 0;       // 先手在整個區間上淨領先即獲勝 / first mover leads => wins

    // 手動釋放記憶體，避免記憶體洩漏。先釋放每一列，再釋放列指標本身。
    // Free memory manually to avoid leaks: free each row, then the array of row pointers.
    for (int i = 0; i < n; i++) free(dp[i]);
    free(dp);

    return aliceWins;                        // 回傳 Alice 是否獲勝 / return whether Alice wins
}

Solution — C++

// 演算法：與 C 版相同的區間 DP。dp[i][j] = 面對 [i..j] 的玩家淨領先分差。
// Algorithm: same interval DP as the C version. dp[i][j] = net lead of the player facing [i..j].
// 轉移取「拿左」「拿右」兩選擇的較大值；dp[0][n-1] > 0 即 Alice 贏。
// Transition = max(take-left, take-right); dp[0][n-1] > 0 means Alice wins.

#include <vector>      // 提供 std::vector，會自動管理記憶體 / gives std::vector, which frees itself
#include <algorithm>   // 提供 std::max / gives std::max

using namespace std;

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();                        // n 是堆數 / number of piles

        // vector<vector<int>> 是「向量的向量」，即自動管理的二維陣列，全部初始化為 0。
        // vector<vector<int>> is a vector of vectors — a self-managing 2D array, all zeros.
        vector<vector<int>> dp(n, vector<int>(n, 0));

        // 基底：單堆時淨領先等於該堆石子數 / base case: single pile -> lead equals its stones.
        for (int i = 0; i < n; i++)
            dp[i][i] = piles[i];

        // 依區間長度由小到大填表 / fill by increasing interval length.
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;                 // 右端索引 / right-end index

                int takeLeft  = piles[i] - dp[i + 1][j];  // 拿左端 / take the left pile
                int takeRight = piles[j] - dp[i][j - 1];  // 拿右端 / take the right pile

                // std::max 回傳兩者較大者，代表最佳選擇 / std::max keeps the better option.
                dp[i][j] = max(takeLeft, takeRight);
            }
        }

        // dp[0][n-1] > 0 表示先手 Alice 最終淨領先 / positive net lead for the first mover.
        return dp[0][n - 1] > 0;
    }
};

複雜度 / Complexity

• Time: O(n²) — 我們填一個 n×n 的表，每個格子 dp[i][j] 只用常數次運算（比較兩個選擇）就算好，格子總數約 n²/2，因此是 O(n²)。n 是石子堆數。/ We fill an n×n table; each cell is computed in O(1) (compare two options), and there are about n²/2 cells, so O(n²). n is the number of piles.
• Space: O(n²) — 二維表 dp 需要 n×n 個整數的空間，這是主要的記憶體開銷。/ The 2D table dp stores n×n integers, which dominates memory usage.

Pitfalls & Edge Cases

• 淨分差 vs 絕對分數 / Net difference vs absolute score： 新手常想分開存 Alice、Bob 的分數，導致狀態變複雜。用「淨領先」把兩個分數合成一個值，是本解法的關鍵；判斷勝負只需看它是否 > 0。/ Beginners try to store both players' scores; folding them into one "net lead" value is the crux, and winning is just > 0.
• 減號的方向 / The minus sign： 轉移式是 piles[i] - dp[i+1][j]，不是加號。因為 dp[i+1][j] 是「對手」的領先，對我而言是落後，所以要減。寫成加號會完全錯。/ The transition subtracts dp[i+1][j] because it is the opponent's lead; using + is a classic bug.
• 填表順序 / Fill order： 必須由短區間往長區間填，否則 dp[i+1][j]、dp[i][j-1] 還沒算好就被讀取，得到錯誤的 0。程式用外層 len 迴圈保證這個順序。/ Must fill short intervals before long ones, or you read uncomputed cells; the outer len loop enforces this.
• 索引越界 / Index bounds： 迴圈條件 i + len - 1 < n 確保 j 不會超出陣列；漏了這個會讀到 piles[n] 造成未定義行為。/ The guard i + len - 1 < n keeps j in range; without it you read piles[n] (undefined behavior).
• C 的記憶體釋放 / Freeing memory in C： C 版用 malloc/calloc 就必須 free，且要先釋放每一列再釋放外層指標，順序反了會存取已釋放的指標。C++ 的 vector 會自動處理，不需手動釋放。/ In C you must free every row then the outer array; C++ vector frees itself.
• 不會平手 / No ties： 題目保證總和為奇數，所以 dp[0][n-1] 不會是 0，> 0 的判斷永遠有明確答案。/ The odd total guarantees dp[0][n-1] != 0, so > 0 always decides cleanly.