0486. Predict the Winner ======================== 题目信息 -------- :题号: 0486 :难度: Medium :主题: 两端取数、两人博弈、累计得分、先手不败 :原题: `LeetCode 0486 `_ :重点: 每回合只能取当前首项或末项、所有元素最终被取完、双方最优、平局也视为玩家 1 获胜 题目重述 -------- 给定非负整数数组 ``nums``。玩家 1 和玩家 2 轮流从当前数组的最左端或最右端取走一个数,并把它加入自己的得分;玩家 1 先行动,直到所有数都被取走。 判断双方都采用最优策略时,玩家 1 是否能够使最终得分大于或等于玩家 2。若两人得分相同,也返回 ``true``。``nums.length`` 位于 ``[1, 20]``,每个元素位于 ``[0, 10^7]``。 自建示例 -------- 先手选择较大端点后获胜: .. code-block:: text 输入:nums = [5,1,2] 输出:true 解释:玩家 1 先取 5;无论玩家 2 之后取哪一端,玩家 1 的最终得分都会高于玩家 2。 先手无法避免失败: .. code-block:: text 输入: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++ 实现 -------- .. code-block:: cpp class Solution { public: bool PredictTheWinner(std::vector& nums) { int n = static_cast(nums.size()); std::vector 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)``。