帖子
- 魔法师2026-08-01
力扣 LeetCode
486. 预测赢家 - 力扣（LeetCode）
486. 预测赢家 - 给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
如果玩家 1 能成为赢家，返回 true...
思路
看题目要么从左取要么从右取，第一时间想到DFS。
因为每个玩家都要用最优策略，所以两者都要计算当前情况下所能取到的最优。
这样会有很多重复计算，为了增加效率，我们把计算过的内部最优结果存起来。
补充说明
- DPS计算当前情况下，当前玩家能取得的最优差值结果。
- 之前的操作对剩余部分的最优结果没有任何影响，所以可以存到Hash里。（所以好像可以用这个规则写DP？）
代码```
class Solution {
private HashMap<Integer, Integer> vis;
public boolean predictTheWinner(int[] nums) {
vis = new HashMap<>();
int res = dps(nums, 0, nums.length - 1, true, 0);
return res >= 0;
}private int dps(int[] nums, int l, int r, boolean first, int flag) {
if (l == r) {
return first ? nums[l] : -nums[l];
}
int left, right;
int lFlag = flag + (1 << l), rFlag = flag + (1 << r);
if (vis.containsKey(lFlag)) {
left = vis.get(lFlag);
} else {
left = dps(nums, l + 1, r, !first, lFlag);
vis.put(lFlag, left);
}
left += (first ? nums[l] : -nums[l]);
if (vis.containsKey(rFlag)) {
right = vis.get(rFlag);
} else {
right = dps(nums, l, r - 1, !first, rFlag);
vis.put(rFlag, right);
}
right += (first ? nums[r] : -nums[r]);
return first ? Math.max(left, right) : -Math.max(-left, -right);
}
}主楼 - Lvvvv2026-08-01
蛮力（```
class Solution {
public:
bool predictTheWinner(vector<int>& nums) {
int n = nums.size();
auto choose = [&](this auto&& choose, int lp, int rp, int sum0, int sum1, bool player) -> bool {
if(lp > rp) {
return sum0 >= sum1;
}
if(!player) {
return choose(lp + 1, rp, sum0 + nums[lp], sum1, !player) | choose(lp, rp - 1, sum0 + nums[rp], sum1, !player);
} else {
return choose(lp + 1, rp, sum0, sum1 + nums[lp], !player) & choose(lp, rp - 1, sum0, sum1 + nums[rp], !player);
}
};
return choose(0, n - 1, 0, 0, 0);
}
}; - SomeBottle2026-08-01
递归解决，注意
dfs是站在玩家 1 视角的。```
class Solution {
public:
bool predictTheWinner(vector<int>& nums) {
// 二者的选择是相互关联的，应该可以动态规划，也可以回溯
auto dfs=[&](auto&& self,int l,int r,int sum1,int sum2,bool current)->bool{
// 根据 current 知道当前轮到 1 (true) 还是 2 (false)
// [l, r] 是这个玩家目前能操作的 nums 范围
if(l>r){
// 递归终点
return sum1>=sum2;
}
if(current){
// 目前是玩家 1，两个分支有一个能赢就行
return self(self,l+1,r,sum1+nums[l],sum2,!current) ||
self(self,l,r-1,sum1+nums[r],sum2,!current);
}else{
// 是玩家 2
// 注意这里是 AND
// 玩家 2 会采用最优策略阻挠玩家 1
// 因此玩家 1 在玩家 2 两个分支下都能赢才算赢
return self(self,l+1,r,sum1,sum2+nums[l],!current) &&
self(self,l,r-1,sum1,sum2+nums[r],!current);
}
};
return dfs(dfs,0,nums.size()-1,0,0,true);
}
}; - 欧拉线2026-08-01
// dp[i] 表示当前玩家在区间 nums[i..j] 上能取得的净胜分（相对对手） // 转移：取左端 nums[i] - dp[i+1]，取右端 nums[j] - dp[i]，取较大者 // 时间 O(n^2)，空间 O(n) bool predictTheWinner(int* nums, int numsSize) { int dp[22] = {0}, len, i; for (len = 1; len <= numsSize; len++) { for (i = 0; i + len <= numsSize; i++) { int j = i + len - 1; int l = nums[i] - (len > 1 ? dp[i + 1] : 0); int r = nums[j] - (len > 1 ? dp[i] : 0); dp[i] = l > r ? l : r; } } return dp[0] >= 0; // 净胜分非负则玩家1赢（平局也算赢） }