486. 预测赢家
题目描述
输入整数数组 nums。玩家 1 和玩家 2 用它玩游戏，两人初始分数都是 0，玩家 1 先行，双方轮流操作。
轮到某人时，他只能拿走当前数组最左端或最右端的一个数，这个数加到他的分数上并从数组中删除。数组被拿空时游戏结束。
两名玩家都会采取让自己得分最多的最优策略。若玩家 1 最终分数大于或等于玩家 2，则视为玩家 1 获胜，返回 true；否则返回 false。
示例 1
输入：nums = [1,5,2] 输出：false
解释：无论玩家 1 先拿 1 还是 2，玩家 2 都会拿走 5，玩家 1 得 3、玩家 2 得 5。
示例 2
输入：nums = [1,5,233,7] 输出：true
解释：玩家 1 先拿 1，之后无论对方拿 5 还是 7，玩家 1 都能拿到 233，以 234 比 12 获胜。
数据范围
1 <= nums.length <= 200 <= nums[i] <= 10^7
解题思路
定义 dp[i][j]：只剩 nums[i..j] 时，当前该取数的人能比对手多拿多少分。如果取左端，得到 nums[i]，然后对手在 [i+1..j] 上比自己多 dp[i+1][j]，净差为 nums[i] - dp[i+1][j]；取右端同理。两者取大。按区间长度从小到大填表，最后看 dp[0][n-1] >= 0。
为什么正确
填 dp[i][j] 时，更短的区间 dp[i+1][j] 与 dp[i][j-1] 都已算好；“分差”的定义让双方共用同一张表。
复杂度分析
时间 O(n^2)，空间 O(n^2)（可压缩到 O(n)）。
易错点
不要用“每次拿两端较大的数”的贪心；[1,5,233,7] 中玩家 1 先拿较小的 1 才是最优。平局算玩家 1 赢，判断用 >= 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def predictTheWinner(self, nums: List[int]) -> bool:
n = len(nums)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = nums[i]
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] >= 0class Solution {
public boolean predictTheWinner(int[] nums) {
int n = nums.length;
long[][] dp = new long[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = nums[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}
}class Solution {
public:
bool predictTheWinner(vector<int>& nums) {
int n = nums.size();
vector<vector<long long>> dp(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) {
dp[i][i] = nums[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}
};func predictTheWinner(nums []int) bool {
n := len(nums)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
dp[i][i] = nums[i]
}
for length := 2; length <= n; length++ {
for i := 0; i+length-1 < n; i++ {
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
}var predictTheWinner = function(nums) {
const n = nums.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = 0; i < n; i++) {
dp[i][i] = nums[i];
}
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
};function predictTheWinner(nums: number[]): boolean {
const n = nums.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = 0; i < n; i++) {
dp[i][i] = nums[i];
}
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}