AlgoPressAppearance
题目描述
https://leetcode.cn/problems/predict-the-winner
给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。
示例 1：
输入：nums = [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：
输入：nums = [1,5,233,7]
输出：true
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。
提示：
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 10^7
思路
本题的乍一看思路是使用贪心算法，必然会赢得比赛，从前面或者后面选择一个大的数，就能赢得比赛。 实际上是不行的，比如 [2,200,3] 玩家1 无论选择1和3，他都会输掉比赛。 但是当总个数位偶数为时，如 [2,200,3,1] 则玩家1可以选择最后一个1，而让玩家2处于刚才的处境，从而玩家1赢得比赛。
所以如何能赢得比赛，应该是玩家1判断取得左边的一个数，或者取得右边的一个数，我自己能得到的最大的分数是多少，然后用总数去减去这个最大的分值，就是对方能取得到最大分值，比较双方分值，则判断玩家1是否能赢得比赛。
至于玩家1取得一个数之后，如何判断自己能得到最大的分支，则使用递归方式。 对方在剩余的分值中肯定会选择最大的值，玩家1要加上小的值。
注意：分值相等也是玩家1赢，所以判断的时候注意使用 >=
参考代码
csharp
public class Solution {
public bool PredictTheWinner(int[] nums) {
//计算总和
int sum = 0;
for(int i=0; i<nums.Length; i++){
sum+=nums[i];
}
int player1 = maxScore(nums,0,nums.Length-1);
int player2 = sum - player1;
return player1 >= player2;
}
private int maxScore(int[] nums, int left, int right){
if(left == right){ //如果只有一个数直接返回，因为只能取得这个值
return nums[left];
}
int leftScore = 0;
int rightScore = 0;
if(right - left == 1){ //如果只有两个数，也可以直接比较取最大值
leftScore = nums[left];
rightScore = nums[right];
}
//如果范围大于两个数，则要收缩
if(right - left > 1){
leftScore = nums[left] + Math.Min(maxScore(nums,left+2,right),maxScore(nums,left+1,right-1)); //对方可以取两边选择大的那个数
rightScore = nums[right] + Math.Min(maxScore(nums,left,right-2),maxScore(nums,left+1,right-1));
}
return Math.Max(leftScore,rightScore);
}
}
参考代码：优化求分值
上述代码中，求 maxScore 的时候，有很多重复计算。 最后还要统计整个sum。 如果我们直接计算 player1 和 player2 获得总分的差值，如果 > 0 则 player 是否可以简化计算呢？
csharp
public class Solution{
public bool PredictTheWinner(int[] nums){
int player1 = maxScoreDiff(nums,0,nums.Length-1);
return player1 >=0 ;
}
private int maxScoreDiff(int[] nums, int left, int right){
if(left == right){ //如果只有一个数，那么只有第一人能拿到，所以差值就是 nums[left]
return nums[left];
}
// 如果只有两个数，比如 5,3 那么差值就是 5-3 = 2， 如果三个数 5,1,3 那么差值就是 5 - (3-1) = 3 就是后面人的差值其实会再加回来
int leftScore = nums[left] - maxScoreDiff(nums,left+1,right);
int rightScore = nums[right] - maxScoreDiff(nums,left,right-1);
return Math.Max(leftScore,rightScore);
}
}
参考代码：优化动态规划
上述计算 maxScoreDiff 的时候，还是有大量的重复计算，如果我们将数据缓存起来，这样就可以把计算换成查询。 定义 dp 二维数组 dp[i,j] 表示从 i到j player1 和 player2 的差值。 初始化 dp[i,i] = nums[i] 因为此时只能 player1 选择这个数值，然后从后往前扩展计算 dp[i,j] 的值 动态转移方程 dp[i,j] = Math.Max(nums[i] - dp[i+1,j], nums[j] - dp[i,j-1])
csharp
public class Solution{
public bool PredictTheWinner(int[] nums){
//定义 dp 数组
int n = nums.Length;
int[,] dp = new int[n,n];
//初始化
for(int i=0; i<n; i++){
dp[i,i] = nums[i];
}
//从后往前递推
for(int i=n-2;i>=0;i--){ //因为要计算至少两个数的差值，所以i从n-2开始，因为i选n-1，j没有数可选
for(int j=i+1;j<n;j++){
dp[i,j] = Math.Max(nums[i]-dp[i+1,j],nums[j]-dp[i,j-1]);
}
}
//最后输出结果，即 [0,n-1] >=0
return dp[0,n-1] >=0;
}
}
参考代码4：优化动归空间
在计算是 dp[i,j] 只用到了 i+1 和 i 行（ dp[i+1,j] 和 dp[i,j-1] ），因为 j = i+1 ，所以可以替换为 j 和 j-1 注意：很难直接说出dp的定义，需要根据上一级二维dp推算出来。
csharp
public class Solution{
public bool PredictTheWinner(int[] nums){
int n = nums.Length;
int[] dp = new int[n];
for(int i=0;i<n;i++){
dp[i] = nums[i];
}
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++){
dp[j] = Math.Max(nums[i]-dp[j],nums[j]-dp[j-1]);
}
}
return dp[n-1] >=0;
}
}