难度：★★★★☆
类型：数组
方法：动态规划
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
题目
给定一个表示分数的非负整数数组。 玩家 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 可以成为赢家。
提示：
1 <= 给定的数组长度 <= 20.
数组里所有分数都为非负数且不会大于 10000000 。
如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。
解答
我们用动态规划解决这一问题。
【数组定义】
定义二维数组dp，维度为n×n，其中n为nums数组的长度，dp[left][right]表示的是从left位置到right位置这个闭区间中的所有数字作为初始数组的话，先手在游戏结束时最终可以超过后手多少分数。dp中的数字可能有正有负，也有零。
【初始状态】
很显然，把所有left=right位置，也就是斜对角线上的位置处的点填充为nums数组中对应位置。因为对于这些点，代表的物理含义是，如果游戏中数组只有一个元素，先手会优于后手多少分？后手没得选了，数组中的数字，就是先手最终优于后手的分数。
【递推公式】
对于left到right的闭区间组成的数组，先手（选手A）有且只有两个选择：
选择left位置处的数字，也就意味着剩下的数字是从left+1到right的闭区间内的，这时候要注意，接下来对于这段区间（从left+1到right），后手（选手B）就变成了先手（尤其要注意，这里理解很重要），而且选手B最终优于选手A的分数为dp[left+1][right]，这样的话，选手A获得了nums[left]分数，减去选手B最终优于选手A的分数，就是选手A最终优于选手B的分数，也就是dp[left][right]=nums[left]-dp[left+1][right]，这里需要理解一下。
另一种状况，选手A拿了最末尾的元素也就是，right所在位置的nums[right]，同理的，这时选手最终会A优于选手B的分数为dp[left][right] = nums[right] - dp[left][right-1]。
我们从这两种情况中选择最大的，作为选手A游戏结束时超过选手B的分数：
dp[left][right] = max(nums[right]-dp[left][right-1], nums[left]-dp[left+1][right])
这里还涉及一个遍历熟悉顺序的问题，left需要从后往前遍历，right需要从前往后遍历，这样做的目的是，充分利用已经被填充的位置的结果，最终填充的dp数组是只有右上的直角三角形。
【返回值】
整个游戏数组最左端是零，结最右端位置是n-1，根据dp数组中每个位置的含义，我们返回dp[0][n-1]作为先手最终超过后手的分数，如果这个分数大于等于零，则先手获胜。
class Solution:
def PredictTheWinner(self, nums) -> bool:
dp = [[nums[i] if i == j else 0 for i in range(len(nums))] for j in range(len(nums))]
for left in reversed(range(len(nums)-1)):
for right in range(left+1, len(nums)):
dp[left][right] = max(nums[right]-dp[left][right-1], nums[left]-dp[left+1][right])
return dp[0][-1] >= 0
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
