解題說明
Predict the Winner
題目描述：兩位玩家輪流從一個整數陣列的兩端取數字，各自累加分數。玩家 1 先手。判斷玩家 1 是否能贏（分數大於或等於玩家 2）。
解題思路：定義 dp[i][j] 為當前玩家面對子陣列 nums[i..j] 時，「自己能比對手多拿的最大分差」。當前玩家可以選左端 nums[i] 或右端 nums[j]。選 nums[i] 後對手面對 [i+1, j]，對手的分差為 dp[i+1][j]，所以當前玩家的淨分差為 nums[i] - dp[i+1][j]。同理選 nums[j] 為 nums[j] - dp[i][j-1]。取兩者的最大值。若 dp[0][n-1] >= 0，玩家 1 獲勝。
C++ 解法
複雜度分析
時間複雜度：O(n^2) — 填充 n x n 的 DP 表格，每個格子 O(1)。
空間複雜度：O(n^2) — DP 表格大小。可優化為 O(n) 使用滾動陣列。
虛擬碼
1. Create dp[n][n], where dp[i][j] = max score difference for current player on nums[i..j]
2. Base case: dp[i][i] = nums[i] (only one element to take)
3. For length = 2 to n:
a. For each start i where j = i + length - 1 < n:
- dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
4. Return dp[0][n-1] >= 0其他解法
記憶化遞迴 O(n^2)：自頂向下計算 dp[i][j]，邏輯相同但用遞迴 + 備忘錄實作。對於不習慣區間 DP 填表順序的人更直觀。
空間優化為 O(n)：觀察到 dp[i][j] 只依賴 dp[i+1][j] 和 dp[i][j-1]，可以用一維陣列滾動更新，將空間從 O(n^2) 降到 O(n)。
延伸思考
- 如果陣列長度為偶數，玩家 1 是否一定不會輸？為什麼？
- 如果不只能從兩端取，而是可以從任意位置取，問題會變成什麼？
- 這個問題與 Stone Game（LeetCode 877）有何關聯和差異？