1406. Stone Game III

題目 / Problem

中文

有一排石頭，第 i 顆石頭的價值是 stoneValue[i]（可能是負數）。Alice 和 Bob 輪流取石頭，Alice 先手。每次輪到某位玩家時，他必須從剩下石頭最前面取走 1、2 或 3 顆。玩家的分數是他取走的所有石頭價值總和，初始都是 0。遊戲進行到石頭全部被取完為止。兩人都採取最優策略（讓自己最終分數盡量高）。請回傳最終誰的分數高："Alice"、"Bob"，或平手 "Tie"。

English

There is a row of stones; stone i has value stoneValue[i] (can be negative). Alice and Bob take turns, Alice first. On a turn, the current player must take 1, 2, or 3 stones from the front of the remaining row. Each player's score is the sum of the values they took (starting at 0). Play continues until all stones are gone. Both play optimally (each maximizing their own final total). Return who ends with the higher score: "Alice", "Bob", or "Tie".

Constraints / 限制 - 1 <= stoneValue.length <= 5 * 10^4 - -1000 <= stoneValue[i] <= 1000

Worked example / 範例 stoneValue = [1,2,3,7] → "Bob". Alice's best first move is taking [1,2,3] (score 6), leaving 7 for Bob (score 7). Bob wins.

名詞解釋 / Glossary

• 動態規劃 / Dynamic programming (DP): A technique that solves a big problem by combining answers to smaller sub-problems, storing each sub-answer once so it is never recomputed. 把大問題拆成小問題，每個小問題只算一次並存起來重用。
• 博弈論 minimax / Game theory minimax: Both players play optimally; one tries to maximize an outcome, the other to minimize it. We model this as one player maximizing the score difference (self minus opponent). 兩人都最優：一方想讓「差值」變大，另一方想讓它變小。
• 分數差 / Score difference: Instead of tracking two separate scores, we track (current player's score − opponent's score). Because the roles swap each turn, this single number captures the whole game. 只追蹤「當前玩家分數減對手分數」這一個數字。
• 後綴 / Suffix (of an array): The part of the array from index i to the end. Our sub-problem is "the game restricted to the suffix starting at i". 從某個位置到結尾的那一段。
• 陣列索引 / Array indexing: stoneValue[i] reads the value at position i (positions start at 0). 讀取第 i 個元素（從 0 開始編號）。
• 指標與 malloc / Pointer & malloc (C): malloc asks the OS for a block of memory and returns a pointer (an address) to it; free gives it back. dp[i] on a pointer means "the value at offset i". malloc 向系統要一塊記憶體並回傳位址；用完要 free。

思路

暴力做法是遞迴模擬：輪到某人時，他可以取 1、2 或 3 顆，各自遞迴下去，選對自己最好的分支。問題在於同一個「剩下從第 i 顆開始」的局面會被重複計算無數次，時間會爆炸到指數級。關鍵觀察是：一個局面的結果只取決於「還剩哪些石頭」，而因為只能從最前面取，剩下的石頭一定是一段後綴，用單一個索引 i 就能完整描述。於是我們定義 dp[i] = 「當輪到某位玩家、且石頭只剩從 i 到結尾時，他能取得的最好『分數差』（自己減對手）」。為什麼用差值而不是兩個分數？因為遊戲對稱：這一步我拿到的石頭算我加分，剩下的局面 dp[i+k] 是對手的最佳差值，對我來說要減掉它。所以 dp[i] = max(對 k=1,2,3：stoneValue[i]+…+stoneValue[i+k-1] − dp[i+k])。邊界是 dp[n]=0（沒石頭時差值為 0）。我們從後往前填表，最後看 dp[0]：大於 0 是 Alice 贏，小於 0 是 Bob 贏，等於 0 平手。這樣每個位置只算一次、每次最多看 3 個選項，時間線性。

The brute force is a recursion: on your turn try taking 1, 2, or 3 stones, recurse on each, and keep the branch best for you. The trap is that the same position — "stones from index i onward" — gets recomputed exponentially many times. The insight: because you can only take from the front, the remaining stones are always a suffix, so a single index i fully describes any position. Define dp[i] = the best score difference (my score minus my opponent's) the player-to-move can guarantee when only stones i..n-1 remain. Why a difference instead of two scores? The game is symmetric: the stones I take now count for me, and the rest of the game dp[i+k] is the opponent's best difference, which is negative from my viewpoint — so I subtract it. That gives dp[i] = max over k∈{1,2,3} of (stoneValue[i]+…+stoneValue[i+k-1] − dp[i+k]), with base case dp[n]=0. Fill the table from right to left, then read dp[0]: positive → Alice, negative → Bob, zero → Tie. Each index is computed once with at most 3 choices, so the whole thing is linear time.

逐步走查 / Walkthrough

Input / 輸入: stoneValue = [1,2,3,7], n = 4. We fill dp[4..0] from right to left. dp[i] = best difference for the player facing stones i..3.

dp[0] = -1 < 0 → Alice's best possible score difference is negative, so Bob wins. Notice at i=0 even Alice's best choice (take [1,2,3], leaving the lone 7 for Bob) still loses by 1 — matching the expected output.

Solution — C

// 演算法 / Algorithm: 後綴 DP（博弈 minimax）。
// dp[i] = 當前玩家面對石頭 i..n-1 時能保證的最佳「分數差」(自己 − 對手)。
// dp[i] = max_{k=1..3} ( 前 k 顆的和 − dp[i+k] )，dp[n] = 0；看 dp[0] 的正負決定勝負。
// Suffix DP: dp[i] is the best (self − opponent) score difference from stones i..n-1.

#include <stdlib.h>   // malloc / free — 動態配置記憶體 / dynamic memory
#include <limits.h>   // LONG_MIN — long 的最小值，當「還沒有最佳值」的起點 / sentinel for "no best yet"

char* stoneGameIII(int* stoneValue, int stoneValueSize) {
    int n = stoneValueSize;                       // n = 石頭數量 / number of stones

    // dp 有 n+1 格：dp[n] 是邊界，其餘 dp[0..n-1] 是各後綴的答案。
    // dp needs n+1 slots: dp[n] is the base case, dp[0..n-1] hold suffix answers.
    // 用 long 避免加總溢位（最多 5e4 顆 × 1000 = 5e7，int 其實夠，但 long 更保險）。
    // Use long to be safe against overflow when summing values.
    long *dp = (long*)malloc(sizeof(long) * (n + 1));

    dp[n] = 0;                                     // 沒有石頭時差值為 0 / no stones left → difference 0

    // 從後往前填表：算 dp[i] 時 dp[i+1..n] 都已就緒。
    // Fill right-to-left so dp[i+1..n] are ready when computing dp[i].
    for (int i = n - 1; i >= 0; i--) {
        long take = 0;                             // take = 目前這一步累計取走的石頭和 / running sum of stones taken this move
        long best = LONG_MIN;                      // best = 目前試過選項中最好的差值 / best difference seen so far

        // k 從 0 開始：k=0 代表取 1 顆、k=1 取 2 顆、k=2 取 3 顆；i+k<n 確保不越界。
        // k=0,1,2 means taking 1,2,3 stones; the i+k<n guard prevents reading past the end.
        for (int k = 0; k < 3 && i + k < n; k++) {
            take += stoneValue[i + k];             // 把第 (i+k) 顆加進本步總和 / add stone (i+k) to this move's sum
            long cur = take - dp[i + k + 1];       // 本步得分 − 對手接手後的最佳差值 / my gain minus opponent's best on the rest
            if (cur > best) best = cur;            // 保留最好的選擇 / keep the best choice
        }
        dp[i] = best;                              // 記錄面對後綴 i 的最佳差值 / store best difference for suffix i
    }

    long res = dp[0];                              // res = 遊戲一開始 Alice 的最佳差值 / Alice's best difference for the whole game
    free(dp);                                      // 歸還記憶體，避免洩漏 / release memory to avoid a leak

    // 差值 > 0 → Alice 分數較高；< 0 → Bob 較高；= 0 → 平手。
    // difference > 0 → Alice higher; < 0 → Bob higher; = 0 → tie.
    if (res > 0) return "Alice";                   // 回傳字串常值即可（LeetCode 接受）/ returning a string literal is fine here
    if (res < 0) return "Bob";
    return "Tie";
}

Solution — C++

// 演算法 / Algorithm: 與 C 版相同的後綴 DP（博弈 minimax）。
// dp[i] = 當前玩家面對石頭 i..n-1 時保證的最佳「分數差」(自己 − 對手)。
// dp[i] = max_{k=1..3}( 前 k 顆和 − dp[i+k] )，dp[n]=0；由 dp[0] 的正負判定勝負。
// Same suffix DP as the C version: dp[0]'s sign decides the winner.

#include <string>       // std::string — 回傳型別 / return type
#include <vector>       // std::vector — 動態陣列，會自動管理記憶體 / auto-managing dynamic array
#include <algorithm>    // std::max — 取兩數較大者 / picks the larger of two values
#include <climits>      // LONG_MIN — 起始哨兵值 / sentinel starting value
using namespace std;

class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {
        int n = stoneValue.size();                 // n = 石頭數量 / number of stones

        // vector<long> 建立 n+1 個元素、全部初始化為 0；dp[n]=0 即為邊界。
        // vector<long> of size n+1, all zero-initialized — dp[n]=0 is already our base case.
        // vector 相比 malloc 的好處：離開作用域自動釋放，不必手動 free。
        // Unlike malloc, a vector frees itself when it goes out of scope — no manual free.
        vector<long> dp(n + 1, 0);

        // 由後往前：算 dp[i] 時，右邊的 dp 都已算好。
        // Right-to-left: when computing dp[i], everything to its right is ready.
        for (int i = n - 1; i >= 0; --i) {
            long take = 0;                         // 本步累計取走的和 / running sum taken this move
            long best = LONG_MIN;                  // 目前最佳差值 / best difference so far

            // k=0,1,2 → 取 1,2,3 顆；i+k<n 防止越界。
            // k=0,1,2 → take 1,2,3 stones; i+k<n keeps us in bounds.
            for (int k = 0; k < 3 && i + k < n; ++k) {
                take += stoneValue[i + k];         // 加入第 (i+k) 顆 / add stone (i+k)
                // std::max 比較「本步兩個候選差值」，留較大者。
                // std::max keeps the larger of the current best and this new option.
                best = max(best, take - dp[i + k + 1]);
            }
            dp[i] = best;                          // 存下後綴 i 的最佳差值 / store best difference for suffix i
        }

        long res = dp[0];                          // 整場遊戲 Alice 的最佳差值 / Alice's best overall difference
        // 用三元/條件回傳字串；差值正負對應勝負。
        // Return the result string based on the sign of the difference.
        if (res > 0) return "Alice";
        if (res < 0) return "Bob";
        return "Tie";
    }
};

複雜度 / Complexity

• Time: O(n) — 我們對每個索引 i（共 n 個）算一次 dp[i]，每次內層迴圈最多只跑 3 個選項（取 1/2/3 顆），是常數。所以總工作量與 n 成正比。We compute dp[i] once for each of the n indices, and each computation examines at most 3 choices — a constant — so total work grows linearly with n (the number of stones).
• Space: O(n) — 需要一個大小為 n+1 的 dp 陣列存所有後綴的答案。We store one dp array of size n+1 holding the answer for every suffix. (可優化成 O(1)：其實只需保留 dp[i+1..i+3] 這 3 個值滾動即可，但用完整陣列比較好懂。Could be reduced to O(1) by keeping only the last 3 values, but the full array is clearer for learning.)

Pitfalls & Edge Cases

• 不要只比分數，要比差值 / Track the difference, not two scores: 若嘗試分別記 Alice 和 Bob 的分數，狀態會變複雜且難以合併。用「當前玩家 − 對手」的單一差值，靠角色對稱把兩人的最優性壓成一個 max。Tracking both scores separately makes the state hard to combine; the single self-minus-opponent difference collapses both players' optimality into one max.
• 負值石頭 / Negative stone values: 石頭可能是負數，所以「取越多越好」是錯的——有時只取 1 顆把爛石頭留給對手更優。best 起始設 LONG_MIN（而非 0）才不會漏掉全是負值的合法選項。Because values can be negative, "take more" is not always better; starting best at LONG_MIN (not 0) ensures an all-negative option isn't wrongly discarded.
• 邊界索引 i+k / Boundary index i+k: 內層迴圈的條件 i + k < n 不可少，否則會讀到 stoneValue 之外的記憶體（未定義行為）。The i + k < n guard is essential — without it you read past the end of stoneValue (undefined behavior).
• dp 大小要 n+1 / dp needs size n+1: 必須有合法的 dp[n] = 0 作為「無石頭」邊界；若只配置 n 格，算 dp[i+k+1] 時會越界。You must have a valid dp[n]=0; allocating only n slots overflows when reading dp[i+k+1].
• 回傳判斷順序 / Return-value logic: 記得 res == 0 是平手 "Tie"，別把 0 誤歸成 Alice 贏（差值要嚴格大於 0 才是 Alice）。res == 0 is a Tie — Alice needs a strictly positive difference to win.
• C 記憶體釋放 / Free in C: C 版用 malloc 就要記得 free，否則記憶體洩漏；C++ 版用 vector 自動管理，不需手動釋放。The C version must free its malloc'd array; the C++ vector cleans up automatically.