1140. Stone Game II

題目 / Problem

中文： Alice 和 Bob 用一排石堆玩遊戲，第 i 堆有 piles[i] 顆石頭（正整數）。兩人輪流拿，Alice 先手。

規則：輪到某人時，可以拿走最前面連續 X 堆的所有石頭，其中 1 <= X <= 2M；拿完後令 M = max(M, X)。一開始 M = 1。遊戲一直進行到石頭被拿光為止。兩人都採取最佳策略，求 Alice 最多能拿到多少石頭。

English: Alice and Bob take turns removing stones from a row of piles; piles[i] is the number of stones in pile i. Alice moves first.

On your turn you take all stones from the first X remaining piles, where 1 <= X <= 2M; then set M = max(M, X). Initially M = 1. The game ends when all stones are gone. With both playing optimally, return the maximum stones Alice can collect.

Constraints / 限制： - 1 <= piles.length <= 100 - 1 <= piles[i] <= 10^4

Worked example / 範例： piles = [2,7,9,4,4] → 10. If Alice takes 1 pile (2), Bob takes 2 piles, then Alice takes the last 2 piles (4+4): Alice gets 2 + 4 + 4 = 10.

名詞解釋 / Glossary

• 後綴和 / Suffix sum：suffix[i] = 從第 i 堆到最後一堆的石頭總和。有了它，任何「從 i 開始剩下的石頭總數」都能 O(1) 查到。 / suffix[i] is the total stones from pile i to the end; lets us get "all stones remaining from index i" in O(1).
• 動態規劃 / Dynamic programming (DP)：把大問題拆成重複出現的小子問題，算過就存起來（記憶化），避免重複計算。 / Break a big problem into overlapping subproblems, store each answer once (memoization), reuse instead of recomputing.
• 狀態 / State：描述一個子問題所需的最少資訊。這題的狀態是 (i, m)：目前輪到的人面對 piles[i:]，且當前 M = m。 / The minimal info describing a subproblem — here (i, m): the mover faces piles[i:] with M = m.
• 記憶化 / Memoization：用一個表 memo[i][m] 記錄已算過的狀態結果，第二次遇到直接回傳。 / A table memo[i][m] caches computed states so we never solve the same one twice.
• 零和賽局 / Zero-sum game：兩人爭同一堆石頭，一人多拿就是另一人少拿。所以「我拿的 = 全部 − 對手拿的」。 / Both fight over the same stones; one player's gain is the other's loss, so mine = total − opponent's.
• 極小化極大 / Minimax：每個玩家都想最大化自己，等價於最小化對手所得——正是零和賽局的核心。 / Each player maximizes their own take, equivalently minimizing the opponent's — the heart of the game.

思路

中文： 先想暴力法：從頭開始，枚舉 Alice 第一步拿 1..2M 堆的每種可能，再枚舉 Bob 的每種回應……這樣會指數爆炸，因為同一個「剩下 piles[i:]、當前 M=m」的局面會被重複計算無數次。

關鍵觀察：一個局面的結果只取決於兩件事——還剩哪些堆（起點 i） 和 當前的 m，跟之前誰拿了什麼、拿的順序都無關。所以狀態只有 (i, m)，且 i, m 都不超過 n，狀態數是 O(n²)，可以用 DP 解。

定義 dp(i, m) = 在「剩 piles[i:]、M=m」時，輪到的那個人最多能拿到的石頭。因為是零和賽局，剩下的石頭總數就是 suffix[i]，如果對手接下來能拿 dp(...)，那我就拿 suffix[i] − dp(...)。於是：

• 若 i + 2m >= n：我可以一口氣把剩下全拿走，dp = suffix[i]。
• 否則枚舉這步拿 X = 1..2m 堆，我拿到 suffix[i] − dp(i+X, max(m, X))，取最大值。

答案就是 dp(0, 1)。用 memo[i][m] 記憶化，每個狀態只算一次，內部迴圈最多 2m ≤ 2n 次，總複雜度 O(n³)，對 n ≤ 100 綽綽有餘。

English: Start with brute force: enumerate every X Alice could take, then every response Bob could make, recursively. This explodes exponentially because the same situation — "piles i: remain, current M=m" — gets recomputed over and over.

The key insight: a position's outcome depends only on which piles remain (start index i) and the current m — not on who took what earlier or in which order. So the state is just (i, m), with both bounded by n, giving O(n²) states — perfect for DP.

Define dp(i, m) = the most stones the player to move can secure when piles[i:] remain and M=m. Since it's zero-sum, the stones still on the table equal suffix[i]; whatever the opponent secures next is dp(...), so I keep suffix[i] − dp(...). Therefore:

• If i + 2m >= n: I can grab everything at once, dp = suffix[i].
• Otherwise try X = 1..2m; I get suffix[i] − dp(i+X, max(m, X)), and take the best.

The answer is dp(0, 1). Memoize with memo[i][m] so each state is solved once; the inner loop runs at most 2m ≤ 2n times, for O(n³) overall — trivial for n ≤ 100.

逐步走查 / Walkthrough

Input piles = [2,7,9,4,4], so n = 5. Suffix sums / 後綴和 suffix = [26, 24, 17, 8, 4, 0] (index 0..5).

Base rule / 基底規則：若 i + 2m >= 5 直接回傳 suffix[i]。

dp(0,1) = 10 → Alice 最多拿 10 顆。/ Alice's optimal total is 10. ✅ (這正對應：Alice 拿 1 堆(2)、Bob 拿 2 堆、Alice 拿最後 2 堆(4+4)=10。 / Alice takes 1, Bob takes 2, Alice takes the last 2 → 2+4+4=10.)

Solution — C

// 演算法 / Algorithm: 動態規劃 + 記憶化 (DP with memoization).
// 狀態 dp(i,m) = 剩 piles[i:]、M=m 時，「輪到的人」最多能拿的石頭。
// 零和賽局：我拿的 = 剩下總和 suffix[i] − 對手能拿的 dp(...)。答案 = dp(0,1)。
// State dp(i,m) = best stones the mover can get from piles[i:] with M=m;
// zero-sum so mine = suffix[i] − opponent's dp(...). Answer = dp(0,1).

static int n;               // 石堆數量 / number of piles
static int suffix[101];     // suffix[i] = piles[i..n-1] 的總和 / suffix sum from i
static int memo[101][101];  // memo[i][m]：算過的答案，-1 表示還沒算 / cached dp, -1 = unset

// 回傳「輪到的人」在狀態 (i,m) 能拿到的最多石頭
// Returns max stones the current mover can secure at state (i,m)
static int dp(int i, int m) {
    if (i >= n) return 0;                 // 沒石頭可拿 / nothing left to take
    if (i + 2 * m >= n)                   // 這步就能把剩下全拿光 / can take all remaining now
        return suffix[i];                 // 全拿 = 剩下總和 / grabbing all = suffix sum
    if (memo[i][m] != -1)                 // 這個狀態算過了 / already solved this state
        return memo[i][m];                // 直接回傳快取 / return cached value

    int best = 0;                         // 目前找到的最大所得 / best take found so far
    // 枚舉這一步拿 X 堆 / try taking X piles this turn, X from 1 to 2m
    for (int x = 1; x <= 2 * m; x++) {
        int nm = (m > x) ? m : x;         // 新的 M = max(m, x) / updated M after taking x
        // 我拿走 piles[i..i+x-1]，對手在 (i+x, nm) 拿 dp()，剩下歸我
        // I take piles[i..i+x-1]; opponent gets dp(i+x,nm); the rest is mine
        int taken = suffix[i] - dp(i + x, nm);
        if (taken > best) best = taken;   // 更新最佳值 / keep the largest
    }
    memo[i][m] = best;                    // 存入快取 / store into cache
    return best;
}

int stoneGameII(int* piles, int pilesSize) {
    n = pilesSize;                        // 記下堆數 / record number of piles
    suffix[n] = 0;                        // 邊界：終點之後總和為 0 / sentinel: sum past the end is 0
    // 由後往前累加，算出每個後綴和 / build suffix sums right-to-left
    for (int i = n - 1; i >= 0; i--)
        suffix[i] = suffix[i + 1] + piles[i];
    // 把整張記憶化表清成 -1（未算） / reset the whole memo table to -1 (unset)
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            memo[i][j] = -1;
    return dp(0, 1);                      // 從頭開始、M=1，求 Alice 的最佳所得 / start at i=0, M=1
}

Solution — C++

// 演算法 / Algorithm: 與 C 版相同的 DP 記憶化 (same memoized DP as the C version).
// dp(i,m) = 剩 piles[i:]、M=m 時輪到的人最多能拿；零和 → mine = suffix[i] − dp(next)。
// dp(i,m) = best the mover can secure from piles[i:] with M=m; answer = dp(0,1).
#include <vector>
#include <algorithm>   // std::max
using namespace std;

class Solution {
    int n;                              // 堆數 / number of piles
    vector<int> suffix;                 // 後綴和 / suffix sums
    vector<vector<int>> memo;           // memo[i][m]，-1 = 未算 / cache, -1 = unset

    int dp(int i, int m) {
        if (i >= n) return 0;                    // 沒石頭 / nothing left
        if (i + 2 * m >= n) return suffix[i];    // 能一次拿光 → 全拿 / take everything remaining
        int &cached = memo[i][m];                // 用參考指向該格，寫回更方便 / reference to the cell
        if (cached != -1) return cached;         // 已算過就回傳 / return if already solved

        int best = 0;                            // 最佳所得 / best take
        for (int x = 1; x <= 2 * m; ++x) {       // 嘗試拿 x 堆 / try taking x piles
            // max(m,x) 更新 M；suffix[i]−dp(...) 是我這條路線能拿的
            // max(m,x) updates M; suffix[i]−dp(...) is my take on this branch
            best = max(best, suffix[i] - dp(i + x, max(m, x)));
        }
        return cached = best;                    // 存入快取並回傳 / cache and return
    }

public:
    int stoneGameII(vector<int>& piles) {
        n = piles.size();                        // 記下堆數 / record size
        suffix.assign(n + 1, 0);                 // 大小 n+1、全填 0（含哨兵）/ size n+1, all zero
        // 由右往左建後綴和 / build suffix sums from right to left
        for (int i = n - 1; i >= 0; --i)
            suffix[i] = suffix[i + 1] + piles[i];
        // (n+1)×(n+1) 的表全初始化為 -1 / init an (n+1)×(n+1) table to -1
        memo.assign(n + 1, vector<int>(n + 1, -1));
        return dp(0, 1);                         // i=0, M=1 開局 / start the game
    }
};

複雜度 / Complexity

• Time: O(n³) — 狀態數為 (i, m) 共 O(n²)（i, m 各最多到 n），每個狀態內部迴圈枚舉 X = 1..2m，最多 O(n) 次；記憶化保證每個狀態只算一次，故 O(n²)·O(n) = O(n³)。n 是石堆數量，n ≤ 100，約 10⁶ 級運算，瞬間完成。 / O(n²) states each doing O(n) work, memoized so computed once → O(n³); n is the pile count (≤ 100).
• Space: O(n²) — memo 表大小 (n+1)×(n+1)；suffix 只需 O(n)；遞迴深度最多 O(n)。主導項是 O(n²)。 / The memo table dominates at (n+1)×(n+1); suffix array O(n), recursion depth O(n).

Pitfalls & Edge Cases

• 零和關係搞反 / Getting the zero-sum wrong：dp 回傳的是「輪到的人」所得，所以我這步的所得必須是 suffix[i] − dp(next)，不是直接加 dp(next)。寫成加法會把對手的所得算成自己的。 / dp returns the mover's take, so my gain is suffix[i] − dp(next); adding instead of subtracting credits the opponent's stones to you.
• M 更新用 max / Updating M：拿 X 堆後是 M = max(M, X)，不是直接設成 X。若當前 m 已比 X 大，錯用 X 會不當縮小可拿範圍。 / After taking X, M = max(M, X), not M = X; overwriting could shrink your allowed range.
• 「能全拿」的邊界 / The "take all" cutoff：判斷式是 i + 2m >= n（用 >=）。若寫成 > 會漏掉「剛好能拿光」的情況，導致遞迴越界或答案錯誤。 / The base case is i + 2m >= n with >=; using > misses the exact-cover case and can over-recurse.
• 記憶化表要重置 / Reset the memo：C 版用全域陣列，必須在每次 stoneGameII 開頭把 memo 清成 -1，否則多組測資會互相污染。C++ 版用成員 vector 並在函式內 assign，天然乾淨。 / With a global array (C), reset memo to -1 each call, or test cases contaminate each other; the C++ member vector is re-assigned so it's clean.
• 不需要擔心溢位 / No overflow worry：總和上限約 100 × 10⁴ = 10⁶，遠在 32-bit int 範圍內，用 int 即可。 / Max total ≈ 10⁶ fits comfortably in a 32-bit int.
• 單堆輸入 / Single pile：piles.length == 1 時 i + 2m = 0 + 2 = 2 >= 1，直接回傳 suffix[0]，Alice 拿走唯一那堆，正確。 / With one pile, the base case fires immediately and Alice takes it — handled correctly.