1、心路历程
这道题最开始想到的做法是回溯，因为看起来遍历就可以做，但是又想到同时需要维护两个人的数据就有点懵了。后来提示说用动态规划做是OK的。
这道题最难的地方在于，需要把输赢建模成“净胜分”，这样就能把两个主体合并为一个主体去动态规划。在明白了这一点之后，5分钟就自己写出来了。
这道题的本质和hot100里那个 乘积最大子数组 需要区分正负数一样，这里也需要区分两个人来分别递推。
2、注意的点
1、注意当递推到第二个人手里时，需要求得是一个最小值而不是最大值。
3、解法 递归动态规划：
class Solution:def predictTheWinner(self, nums: List[int]) -> bool:n = len(nums)@cachedef dp(i, j, k): # i - j 区间的最大净胜值 k = 1代表先手者 否则是后手者if j - i == 0:if k == 1:return nums[i]else:return - nums[i]if k == 1:return max(nums[i] + dp(i+1, j, 0), nums[j] + dp(i, j-1, 0))else:return min(-nums[i] + dp(i+1, j, 1), - nums[j] + dp(i, j-1, 1))return dp(0, n-1, 1) >= 0
