0486. Predict the Winner¶
题目信息¶
- 题号:
0486
- 难度:
Medium
- 主题:
两端取数、两人博弈、累计得分、先手不败
- 原题:
- 重点:
每回合只能取当前首项或末项、所有元素最终被取完、双方最优、平局也视为玩家 1 获胜
题目重述¶
给定非负整数数组 nums。玩家 1 和玩家 2 轮流从当前数组的最左端或最右端取走一个数,并把它加入自己的得分;玩家 1 先行动,直到所有数都被取走。
判断双方都采用最优策略时,玩家 1 是否能够使最终得分大于或等于玩家 2。若两人得分相同,也返回 true。nums.length 位于 [1, 20],每个元素位于 [0, 10^7]。
自建示例¶
先手选择较大端点后获胜:
输入:nums = [5,1,2]
输出:true
解释:玩家 1 先取 5;无论玩家 2 之后取哪一端,玩家 1 的最终得分都会高于玩家 2。
先手无法避免失败:
输入:nums = [4,7,2]
输出:false
解释:玩家 1 无论先取 4 还是 2,玩家 2 都能取走中间的 7,最终玩家 1 得 6、玩家 2 得 7。
区间博弈保存当前玩家的得分差¶
定义 dp[i] 为当前玩家面对区间 [i, j] 时,相对另一名玩家最多能取得的分数差。若取左端,收益是 nums[i] - dp[i+1];若取右端,收益是 nums[j] - dp[i],因为取走后轮到对手,原本的优势要被对手在剩余区间取得的最优差值抵消。
按区间长度从 2 增长,并让 dp[i+1] 仍保留上一长度的值,就能把二维状态压缩成一维。最终 dp[0] >= 0 表示先手至少不输,平局也符合题意。
C++ 实现¶
class Solution {
public:
bool PredictTheWinner(std::vector<int>& nums) {
int n = static_cast<int>(nums.size());
std::vector<long long> dp(nums.begin(), nums.end());
for (int length = 2; length <= n; ++length) {
for (int left = 0; left + length <= n; ++left) {
int right = left + length - 1;
long long takeLeft = nums[left] - dp[left + 1];
long long takeRight = nums[right] - dp[left];
dp[left] = std::max(takeLeft, takeRight);
}
}
return dp[0] >= 0;
}
};
代码分析¶
每个区间只保留当前玩家相对对手的最优差值,取端点后的“轮到对手”由减法体现;一维更新顺序保证两个子区间状态仍未被覆盖。状态数为 O(n^2),时间复杂度为 O(n^2),空间复杂度压缩为 O(n)。