486. Predict the Winner

題目 / Problem

中文： 給你一個整數陣列 nums。兩位玩家（玩家 1 和玩家 2）用這個陣列玩遊戲，玩家 1 先手。兩人初始分數都是 0。每一回合，當前玩家從陣列的最左端 (nums[0]) 或最右端 (nums[nums.length - 1]) 取走一個數字，加到自己的分數上，陣列長度隨之減 1。當陣列取空時遊戲結束。若玩家 1 的最終分數大於等於玩家 2，回傳 true（分數相等也算玩家 1 贏），否則回傳 false。假設兩人都採取最佳策略。

English： You are given an integer array nums. Two players take turns, player 1 first, both starting at score 0. On each turn the current player takes a number from either end of the array (nums[0] or nums[nums.length - 1]), adds it to their score, and the array shrinks by one. The game ends when the array is empty. Return true if player 1's final score is greater than or equal to player 2's (a tie still counts as a player-1 win); otherwise false. Both players play optimally.

Constraints： - 1 <= nums.length <= 20 - 0 <= nums[i] <= 10^7

Worked example： nums = [1,5,233,7] → true. Player 1 picks 1; player 2 must pick from 5 or 7; either way player 1 then grabs 233. Final: player 1 = 234, player 2 = 12, so player 1 wins.

名詞解釋 / Glossary

• 博弈論 / Game theory：研究「雙方都做最聰明選擇」的數學。這裡兩位玩家都想讓自己最終分數最高，所以每一步都選對自己最有利的。/ The math of two rational players each making the best possible move for themselves.
• 動態規劃 / Dynamic programming (DP)：把大問題拆成一堆重疊的小問題，把每個小問題的答案存進表格，避免重複計算。/ Breaking a big problem into overlapping smaller ones and storing each sub-answer in a table so it's computed only once.
• 子陣列 / Subarray：原陣列中一段連續的區間，例如 nums[i..j]。因為每次只能從兩端取，剩下的永遠是一段連續區間。/ A contiguous slice nums[i..j]. Since we only remove from the ends, what remains is always contiguous.
• 分數差 / Score difference：本題核心技巧。我們不分別追蹤兩人的分數，而是追蹤「當前玩家的分數 − 對手的分數」。差值 ≥ 0 就代表當前玩家不會輸。/ Instead of tracking both scores, we track (current player's score − opponent's score). A difference ≥ 0 means the current player doesn't lose.
• 二維陣列 / 2D array：像表格一樣用兩個索引 dp[i][j] 定位一格，這裡代表「面對子陣列 nums[i..j] 時能拿到的最佳分數差」。/ A table indexed by two numbers; here dp[i][j] holds the best score difference achievable on subarray nums[i..j].

思路

最直覺的做法是暴力遞迴：模擬每一步，當前玩家試「取左端」和「取右端」兩種選擇，各自遞迴下去，回傳讓自己贏面最大的那條路。但這樣同一個子陣列會被重複計算無數次，n=20 時可能爆炸。關鍵的簡化是：我們不需要分別記兩人的分數，只需要記分數差。定義 dp[i][j] = 當只剩下子陣列 nums[i..j]、且輪到某玩家先取時，這位玩家能保證的「自己分數減對手分數」的最大值。為什麼追蹤差值就夠？因為遊戲是對稱的——不管現在是玩家 1 還是玩家 2 在取，他都只想最大化自己領先的幅度。當前玩家有兩個選擇：取左端 nums[i]，那麼剩下 nums[i+1..j] 就輪到對手，對手在那段能拿到的最佳差值是 dp[i+1][j]，而對手的優勢就是我的劣勢，所以我這條路的差值是 nums[i] - dp[i+1][j]；同理取右端得到 nums[j] - dp[i][j-1]。兩者取較大值即 dp[i][j]。base case 是 dp[i][i] = nums[i]（只剩一個數，直接拿走）。我們按子陣列長度由小到大填表，最後 dp[0][n-1] >= 0 就表示先手玩家 1 不會輸。

The naive approach is brute-force recursion: simulate every move, letting the current player try both "take left" and "take right", recurse on each, and keep whichever wins them more. But the same subarray gets recomputed exponentially, which blows up near n=20. The key simplification is that we don't need each player's score separately — only their difference. Define dp[i][j] as the maximum value of (my score − opponent's score) the player-to-move can guarantee when only nums[i..j] remains. Why is the difference enough? The game is symmetric: whoever is choosing only cares about maximizing their own lead. The current player has two options. Take the left, nums[i]: the opponent then faces nums[i+1..j] and secures dp[i+1][j] for themselves — but their lead is my deficit, so this path yields nums[i] - dp[i+1][j]. Symmetrically, taking the right yields nums[j] - dp[i][j-1]. We pick the larger: dp[i][j] = max(...). The base case is dp[i][i] = nums[i] (one number left — just grab it). We fill the table by increasing subarray length, and finally dp[0][n-1] >= 0 means first-mover player 1 does not lose.

逐步走查 / Walkthrough

Input: nums = [1, 5, 2], n = 3.

Base case（長度 1 / length-1 subarrays）:

len = 2:

len = 3:

結論 / Result: dp[0][2] = -2，-2 >= 0 為假 / is false → return false. ✅ Matches the expected output.

Solution — C

// 演算法 / Algorithm:
// 用區間 DP 追蹤「分數差」。dp[i][j] = 當只剩 nums[i..j]、輪到某玩家先取時，
// 他能保證的 (自己分數 - 對手分數) 的最大值。轉移取左或取右兩種選擇的較大者。
// Interval DP over score difference; dp[i][j] = best (my - opponent) score gap
// the mover can guarantee on nums[i..j]. Answer is dp[0][n-1] >= 0.

#include <stdbool.h>   // 讓 bool / true / false 可用 / brings in bool, true, false

bool predictTheWinner(int* nums, int numsSize) {
    int n = numsSize;                 // n 是陣列長度，寫短一點方便閱讀 / array length, short alias

    // dp 是二維表格；n <= 20 所以固定開 20x20 綽綽有餘
    // dp is a 2D table; n <= 20 so a fixed 20x20 array is plenty
    int dp[20][20];

    // Base case：子陣列只有一個元素時，先取者直接拿走它，差值就是該值本身
    // Base case: on a length-1 subarray the mover just takes it; the gap is that value
    for (int i = 0; i < n; i++)       // 逐一設定對角線 dp[i][i] / fill the diagonal
        dp[i][i] = nums[i];

    // 依子陣列長度 len 由小到大填表，確保用到的較短區間都已算好
    // Fill by increasing length so shorter subarrays (which we depend on) are ready
    for (int len = 2; len <= n; len++) {
        // i 是子陣列左端點；j = i+len-1 是右端點，需保證 j 不越界
        // i is the left end; j = i+len-1 is the right end, kept in-bounds
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;      // 右端點索引 / right endpoint index

            // 選擇 A：取走左端 nums[i]，剩 nums[i+1..j] 留給對手，
            // 對手優勢 dp[i+1][j] 就是我的劣勢，故差值 = nums[i] - dp[i+1][j]
            // Option A: take nums[i]; opponent's edge dp[i+1][j] is my loss
            int pickLeft  = nums[i] - dp[i + 1][j];

            // 選擇 B：取走右端 nums[j]，剩 nums[i..j-1] 留給對手，同理
            // Option B: take nums[j]; symmetric reasoning
            int pickRight = nums[j] - dp[i][j - 1];

            // 當前玩家選對自己最有利（差值最大）的那一種 / mover picks the larger gap
            dp[i][j] = pickLeft > pickRight ? pickLeft : pickRight;
        }
    }

    // 整個陣列 nums[0..n-1] 上先手（玩家 1）的最佳差值 >= 0 就代表不會輸
    // If player 1's best gap over the whole array is >= 0, they don't lose
    return dp[0][n - 1] >= 0;
}

Solution — C++

// 演算法 / Algorithm:
// 與 C 版相同的區間 DP：dp[i][j] = 面對子陣列 nums[i..j] 時，先取者能保證的
// (自己 - 對手) 最大分數差。取左 / 取右擇優，最後看 dp[0][n-1] >= 0。
// Same interval DP as the C version over the score difference.

#include <vector>      // std::vector 動態陣列 / dynamic array container
using namespace std;

class Solution {
public:
    bool predictTheWinner(vector<int>& nums) {
        int n = nums.size();          // .size() 回傳元素個數 / number of elements

        // vector<vector<int>> 是「二維陣列」；建一個 n x n、初值全 0 的表格
        // A 2D vector (rows of ints); n x n, all initialized to 0
        vector<vector<int>> dp(n, vector<int>(n, 0));

        // Base case：長度為 1 的區間，先取者直接拿走該數
        // Base case: on a single-element subarray, just take that number
        for (int i = 0; i < n; ++i)
            dp[i][i] = nums[i];

        // 由短到長填表；短區間先算好，長區間才能引用它們
        // Build up by length so longer subarrays can reuse shorter results
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;  // 右端點 / right endpoint

                // 取左端：對手在 nums[i+1..j] 的優勢就是我的劣勢
                // Take left: opponent's advantage on nums[i+1..j] counts against me
                int pickLeft  = nums[i] - dp[i + 1][j];

                // 取右端：對手在 nums[i..j-1] 的優勢就是我的劣勢
                // Take right: symmetric
                int pickRight = nums[j] - dp[i][j - 1];

                // std::max 回傳兩者中較大值 / max returns the larger of the two
                dp[i][j] = max(pickLeft, pickRight);
            }
        }

        // 先手在整段陣列上的最佳差值 >= 0 即玩家 1 不會輸
        // Player 1 doesn't lose iff their best whole-array gap is >= 0
        return dp[0][n - 1] >= 0;
    }
};

複雜度 / Complexity

• Time: O(n²) — 表格有 n × n 個格子，每格只做常數次比較與加減就填好，所以總時間由格子數主導，n 是陣列長度。/ The table has n × n cells and each is filled in constant time, so runtime is dominated by the number of cells; n is the array length.
• Space: O(n²) — 需要一個 n × n 的 DP 表格存所有子區間的答案。（進階：可壓成一維 O(n)，但二維對初學者更好理解。）/ We store the full n × n DP table. (It can be squeezed to a 1D O(n) rolling array, but 2D is clearer for beginners.)

Pitfalls & Edge Cases

• 回傳條件是 >= 0 而非 > 0 / Return >= 0, not > 0：題目規定平手也算玩家 1 贏，差值為 0 必須回傳 true；寫成 > 0 會在平局時誤判。/ Ties count as a player-1 win, so a zero gap must return true; > 0 would wrongly fail on ties.
• 索引順序：務必由短區間往長區間填 / Fill short-to-long：dp[i][j] 依賴 dp[i+1][j] 與 dp[i][j-1]（都是更短的區間）。若填表順序錯誤，會讀到還沒計算的格子，得到垃圾值。/ dp[i][j] depends on shorter subarrays; a wrong fill order reads uninitialized cells.
• 單一元素 n=1 / Single element：只有一個數字時玩家 1 直接拿走、玩家 2 得 0 分，dp[0][0] = nums[0] >= 0 恆為 true，程式自然處理，無須特判。/ With one number player 1 takes it and wins; the base case handles this with no special-casing.
• 用分數差而非分別記分 / Track the gap, not two scores：新手常想同時追蹤兩人分數，狀態會變複雜且易錯。追蹤差值把「對手最佳」直接變成「我的最差」，一個數字就概括了局面。/ Beginners often track both scores; the difference trick folds "opponent's best" into "my worst" with a single number.
• 溢位 / Overflow：nums[i] <= 10^7 且最多 20 個，總和最多約 2×10^8，遠在 32 位元 int（約 2.1×10^9）範圍內，不會溢位。/ Max total ≈ 2×10^8, well within 32-bit int, so no overflow.