🚩传送门：https://leetcode-cn.com/problems/predict-the-winner/

题目

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数 总和 最多的玩家获胜。

给定一个表示分数的数组，预测 玩家1 是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：

输入：[1, 5, 2] 输出：False 解释：一开始，玩家1 可以从 1 和 2 中进行选择。如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。因此，玩家 1 永远不会成为赢家，返回 False 。

示例 2：

输入：[1, 5, 233, 7] 输出：True 解释：玩家1 一开始选择 1 。然后玩家2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。最终，玩家1（234 分）比玩家2（12 分）获得更多的分数，所以返回 True，表示玩家1 可以成为赢家。

解题思路：递归

为了判断哪个玩家可以获胜，需要计算一个总分，即先手得分与后手得分 之差。当数组中的所有数字都被拿取时，如果总分大于或等于 0，则先手获胜，反之则后手获胜。

每次只从数组的任意一端拿取数字，因此利用双指针滑动可以保证指针间一定是连续的。假设数组当前剩下的部分为下标 到下标 ，其中 。

若 ，则只剩一个数字，当前玩家只能拿取这个数字。
若 ，则当前玩家可以选择 或 ，另一个玩家在数组剩下的部分选取

计算总分时，需要记录当前玩家是先手还是后手，判断当前玩家的得分应该记为正还是负。
[LeetCode]Dp486 预测赢家 [滚动数组] - 图1

复杂度分析

时间复杂度：，其中 [LeetCode]Dp486 预测赢家 [滚动数组] - 图2 为数组 的长度 。

空间复杂度：，其中 [LeetCode]Dp486 预测赢家 [滚动数组] - 图3 为数组 的长度。空间复杂度取决于递归使用的栈空间。

代码

🚩官方代码

  1. class Solution {
  2.     public boolean PredictTheWinner(int[] nums) {
  3.         return total(nums, 0, nums.length - 1, 1) >= 0;
  4.     }
  6.     public int total(int[] nums, int start, int end, int turn) {
  7.         if (start == end) {
  8.             return nums[start] * turn;
  9.         }
  10.         int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
  11.         int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
  12.         return Math.max(scoreStart * turn, scoreEnd * turn) * turn;
  13.     }
  14. }

解题思路：动态规划

👉 定义 为在区间 里，当前玩家与另一个玩家的分差的最大值 ，当前玩家不一定是先手。

不难发现只有当 时，数组剩下的部分才有意义，因此当 时，。

  1. 当 时，只剩一个数，只能取此数，故对于 ，有
  2. 当 时，当前玩家可以选择 或 ，然后轮到另一个玩家在剩余数字中选取。
    • 两种方案中，当前玩家会选择最优方案，使自己的分数最大化。因此可以推出状态转移方程。
  3. 最后判断 的值，如果大于或等于 ，则先手得分大于或等于后手得分，因此先手成为赢家，否则后手成为赢家。

状态转移方程：

image.png
图解

QQ录屏20210622222845.mp4

复杂度分析

时间复杂度：，其中 [LeetCode]Dp486 预测赢家 [滚动数组] - 图6 为数组 的长度 。需要计算每个子数组对应的 的值，所以共

有 个子数组。

空间复杂度：，其中 [LeetCode]Dp486 预测赢家 [滚动数组] - 图7 为数组 的长度。若使用一维滚动数组优化可以降至 。

代码

🚩官方代码

  1. class Solution {    
  2.     public boolean PredictTheWinner(int[] nums) {
  3.         int length = nums.length;
  4.         int[][] dp = new int[length][length];
  5.         for (int i = 0; i < length; i++) {
  6.             dp[i][i] = nums[i];
  7.         }
  8.         for (int i = length - 2; i >= 0; i--) {
  9.             for (int j = i + 1; j < length; j++) {
  10.                 //状态转移方程
  11.                 dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
  12.             }
  13.         }
  14.         return dp[0][length - 1] >= 0;
  15.     }
  16. }

滚动数组优化
image.pngimage.png
代码中使用了二维数组 dp。分析状态转移方程可以看到，dp[i][j] 的值只和 dp[i+1][j] 与 dp[i][j−1] 有关，即在计算 dp 的第 i 行的值时，只需要使用到 dp 的第 i 行和第 i+1 行的值，因此可以使用滚动数组对空间进行优化。

  1. class Solution {
  2.     public boolean PredictTheWinner(int[] nums) {
  3.         int length = nums.length;
  4.         int[] dp = new int[length];
  5.         //初始化dp数组
  6.         for (int i = 0; i < length; i++) {
  7.             dp[i] = nums[i];
  8.         }
  9.         //外循环次数
  10.         for (int i = length - 2; i >= 0; i--) {
  11.             //内循环
  12.             for (int j = i + 1; j < length; j++) {
  13.                 //状态转移方程
  14.                 dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
  15.             }
  16.         }
  17.         return dp[length - 1] >= 0;
  18.     }
  19. }