486. 预测赢家 - medium
给定一个表示分数的非负整数数组。 玩家 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 仍为赢家。
思路：
· 参考《零和博弈！记忆化 0ms 搞定 ~》。
· 动态规划，零和博弈，让自己最优和让对手最差其实是相同的目标！原因，双方得分的总和即为 nums 的累加和不变，自己多了，对手必然减少；
· 问题转化，变为：先手如何让对手的最终得分最少，在零和博弈问题中，一般会存在先手优势和后手劣势；
· 先手优势：因为先手可以先走，所以可决定后手将要面对的局面。因此，后手虽然也会做出最优解，但是先手可以根据先发的优势，让后手进入最优解最差的局面。
· 后手劣势：当先手走完后，虽然后手也会成为下一回合的先手，也可以做出最优解，但后手无法选择下一回合的局面。
· 我们设 optimal(L, R) 为在 nums[L:R] 这种局面上，先手的最优得分。这里的先手抛开了自己或者对手的概念，先手就是指在这种局面上第一个出手的那个人！
· 当 L == R 时，因为只有一个数字，显然不需要做抉择了，optimal(L, R) 即为 nums[L]。
· 当 L < R 时，先手有两种选择：
○ 先手选择 nums[L], 让该回合的后手进入 optimal(L 1, R) 局面。
○ 先手选择 nums[R], 让该回合的后手进入 optimal(L, R-1) 局面。
○ optimal(L, R) = sum(L, R) - min(optimal(L 1, R), optimal(L, R-1))。sum(L, R) 表示 nums[L:R] 的累加和，min() 表示让对手进入最高分最低的那个局面。
· 图例：
· 和 “516.最长回文子序列”类似，dp[i][j]，即，在二维数组 dp 中，i,j 的下标表示的是 nums 的起始终止位置，这个一定要理解。
· 因为要先算只有一个值的情况，再慢慢扩大到全局的情形，所以要从后往前算。
class Solution { public boolean PredictTheWinner(int[] nums) { int n = nums.length; int[][] dp = new int[n][n]; // dp[i][j] 表示nums[i:j]区间的最优解 for(int i = 0; i < n; i ) dp[i][i] = nums[i];//只有一个值的，先手全拿 for(int i = n-2; i >= 0; i--){ //从 n-2 开始，因为防止 i 1 溢出 for(int j = i 1; j < n; j ){ int sum = numsSum(nums, i, j); //nums[left:right] 的和 dp[i][j] = sum - Math.min(dp[i 1][j], dp[i][j-1]); // 总和 - 让对手最优值最小的情况 } } return dp[0][n-1] * 2 >= numsSum(nums, 0, n-1); //先手拿到的分数是否超过总分的一半 } public int numsSum(int[] nums, int left, int right){ //数组left~right的和 int sum = 0; for(int i = left; i <= right; i ) sum = nums[i]; return sum; }}