LeetCode 解題筆記：486. Predict the Winner

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


LeetCode 題目連結：486. Predict the Winner

解題想法

中等難度題。題目給一個陣列 $nums$，兩個玩家 A、B 每次行動時可以從 $nums$ 兩端選取並移除一個數字，獲得這個數字的分數，玩家 A 先行動，如果玩家 A 總分大於等於玩家 B，回傳 True。這題很適合用動態規畫解題，建立一個 $n \times n$ 的二維陣列 $dp[i][j]$ 代表可選數字剩下 $nums[i]$ ~ $nums[j]$ 時目前行動玩家與另一人的最大分差。更新狀態時有 2 種選擇：

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

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

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.11 MB, beats 94.32%.

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        # 初始化 dp
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = nums[i]
        # 由長度 2 開始填表格，直到長度 n 為止
        for length in range(2, n+1):
            for i in range(n - length + 1):  # 起點
                j = i + length - 1  # 終點
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
        # 回傳答案
        return dp[0][n-1] >= 0

C++ 程式碼

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

class Solution {
public:
    bool predictTheWinner(vector<int>& nums) {
        int n = (int)nums.size();
        // 初始化 dp
        vector<vector<int>> dp (n, vector<int> (n, 0));
        for(int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
        }
        // 由長度 2 開始填表格，直到長度 n 為止
        for(int length = 2; length <= n; length++) {
            for(int i = 0; i <= n - length; i++) {  // 起點
                int j = i + length - 1;  // 終點
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
            }
        }
        // 回傳答案
        return dp[0][n-1] >= 0;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.55 MB, beats 79.49%.

bool predictTheWinner(int* nums, int numsSize) {
    int dp[21][21];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < numsSize; i++) {
        dp[i][i] = nums[i];
    }
    for(int length = 2; length <= numsSize; length++) {
        for(int i = 0; i <= numsSize - length; i++) {
            int j = i + length - 1;
            int left = nums[i] - dp[i+1][j];
            int right = nums[j] - dp[i][j-1];
            if (left >= right) dp[i][j] = left;
            else dp[i][j] = right;
        }
    }
    return dp[0][numsSize-1] >= 0;
}