题目
给定一个表示分数的非负整数数组。 玩家 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 仍为赢家。
分析
首先分析就是使用递归
方法一：暴力递归（正常思路）
public boolean PredictTheWinner(int[] nums) {
// 模拟真实情况下，A，B轮流选牌的过程，求出结果
return dfs(0, nums.length - 1, 0, 0, true, nums);
}
//分别为 左边可取的位置，右边可取的位置，A的得分，B的得分， 轮到谁选牌， nums数组
private static boolean dfs(int left, int right, int sumA, int sumB, boolean to_A, int[] nums) {
// TODO Auto-generated method stub
if(left > right) {//左右越界，没有牌了，比较得分，判断胜负（以A为主角）
return sumA >= sumB;
}
if(to_A) {//轮到A选牌,A是主角，只要左边或者右边有一种必胜情况，就说明可以必胜
return dfs(left + 1, right, sumA + nums[left], sumB, false, nums) || dfs(left, right - 1, sumA + nums[right], sumB, false, nums);
}else {//轮到B选牌，不管B怎么选，此时只有左右两边都保证A是必胜的，才能保证A最终必胜
return dfs(left + 1, right, sumA, sumB+ nums[left], true, nums) && dfs(left, right - 1, sumA, sumB + nums[right], true, nums);
}
}
方法二：递归（思路一）
分析
为了判断哪个玩家可以获胜，需要计算一个总分，为先手得分与后手得分之差。当数组中的所有数字都被拿取时，如果总分大于或等于 0，则先手获胜，反之则后手获胜。
由于每次只能从数组的任意一端拿取数字，因此可以保证数组中剩下的部分一定是连续的。假设数组当前剩下的部分为下标start 到下标end，其中 0 ≤ start ≤ end < nums . length 0 \le \textit{start} \le \textit{end} < \textit{nums}.\text{length} 0≤start≤end<nums.length。如果 start = end \textit{start}=\textit{end} start=end，则只剩一个数字，当前玩家只能拿取这个数字。如果 start < end \textit{start}<\textit{end} start<end，则当前玩家可以选择$ nums [ start ] \textit{nums}[\textit{start}] nums[start]$ 或 nums [ end ] \textit{nums}[\textit{end}] nums[end]，然后轮到另一个玩家在数组剩下的部分选取数字。这是一个递归的过程。
计算总分时，需要记录当前玩家是先手还是后手，判断当前玩家的得分应该记为正还是负。当数组中剩下的数字多于 1 个时，当前玩家会选择最优的方案，使得自己的分数最大化，因此对两种方案分别计算当前玩家可以得到的分数，其中的最大值为当前玩家最多可以得到的分数。
public boolean PredictTheWinner(int[] nums) {
return total(nums, 0, nums.length - 1, 1) >= 0;
}
public int total(int[] nums, int start, int end, int turn) {
if (start == end) {
return nums[start] * turn;
}
int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
return Math.max(scoreStart * turn, scoreEnd * turn) * turn;
}
方法三：递归（思路二）
分析
以 [1, 5, 233, 7] 为例，玩家 1 先手。
如果玩家 1 先选左端 1，则玩家 2 在 [5, 233, 7] 的两端中选。
如果玩家 1 先选右端 7，则玩家 2 在 [1, 5, 233] 的两端中选。
可以看到，每个节点都是其中一个玩家在选择。当前子问题下，谁的分数更多，谁就赢。
当前，你选了 x，得 x 分，他没选，得 0分，你赢了别人 x 分，接下来呢？他选，然后你选……你们交替地得分……打住，你已进入递归的细节，别想下去了。
当前你有 x 分，对手 0 分，在后面的游戏中，对手拢共超过你 y 分，如果 x >= y，那你赢咯。
别操心递归的细节，细节丢给子调用去做，眼睛盯着当前的 x 分，想想子调用应该返回什么，去和当前的 x 分作比较，判断出胜利。
于是，递归函数做的事：计算当前做选择的玩家能赢过对手的分数。如果大于零，则表示他在这个子问题中赢了。
怎么计算呢？当前选择的分数，减去，接下来对手赢过自己的分数（剩余数组的递归结果），因为选择有两种，所以我们二者取其大。
public boolean PredictTheWinner2(int[] nums) {
return help(0, nums.length - 1, nums) >= 0;
}
private static int help(int left, int right, int[] nums) {
// TODO Auto-generated method stub
if(left == right) {
return nums[left];
}
int sumL = nums[left] - help(left + 1, right, nums); // 选择左端
int sumR = nums[right] - help(left, right, nums);// 选择右端
return Math.max(sumL, sumR);
}
方法四：记忆化递归（思路优化）
分析
我们做了哪些重复的计算呢？
比如，你先选 1，我再选 7，和你先选 7，我再选 1，这两种所带来的子问题是一样的，都是剩下[5, 233]。我们用数组或哈希表去存储计算过的子问题的解，下次遇到重复的子问题，就不用再次递归计算。
public static boolean PredictTheWinner3(int[] nums) {
int len = nums.length;
int[][] memo = new int[len][len];
for(int i = 0; i < len; i++) {
Arrays.fill(memo[i], Integer.MIN_VALUE);
}
return dfs2(nums, 0, len - 1, memo) >= 0;
}
public static int dfs2(int[] nums, int left, int right, int[][] memo) {
if(left > right) {
return 0;
}
if(memo[left][right] != Integer.MIN_VALUE) {
return memo[left][right];
}
int Left = nums[left] - dfs2(nums, left + 1, right, memo);
int Right = nums[right] - dfs2(nums, left, right - 1, memo);
memo[left][right] = Math.max(Left, Right);
return memo[left][right];
}
方法五：动态规划
分析
定义二维数组 dp \textit{dp} dp，其行数和列数都等于数组的长度， dp [ i ] [ j ] \textit{dp}[i][j] dp[i][j]表示当数组剩下的部分为下标 i 到下标 j 时，当前玩家与另一个玩家的分数之差的最大值，注意当前玩家不一定是先手。
只有当 i ≤ j i \le j i≤j时，数组剩下的部分才有意义，因此当 i > j i>j i>j时， dp [ i ] [ j ] = 0 \textit{dp}[i][j]=0 dp[i][j]=0。
当 i=j时，只剩一个数字，当前玩家只能拿取这个数字，因此对于所有 0 ≤ i < nums . length 0 \le i < \textit{nums}.\text{length} 0≤i<nums.length，都有 dp [ i ] [ i ] = nums [ i ] \textit{dp}[i][i]=\textit{nums}[i] dp[i][i]=nums[i]。
当 i<j时，当前玩家可以选择 nums [ i ] \textit{nums}[i] nums[i] 或 nums [ j ] \textit{nums}[j] nums[j]，然后轮到另一个玩家在数组剩下的部分选取数字。在两种方案中，当前玩家会选择最优的方案，使得自己的分数最大化。因此可以得到如下状态转移方程：
dp [ i ] [ j ] = max ( nums [ i ] − dp [ i + 1 ] [ j ] , nums [ j ] − dp [ i ] [ j − 1 ] ) \textit{dp}[i][j]=\max(\textit{nums}[i] - \textit{dp}[i + 1][j], \textit{nums}[j] -\textit{dp}[i][j - 1]) dp[i][j]=max(nums[i]−dp[i+1][j],nums[j]−dp[i][j−1])
最后判断 dp [ 0 ] [ nums . length − 1 ] \textit{dp}[0][\textit{nums}.\text{length}-1] dp[0][nums.length−1] 的值，如果大于或等于 0，则先手得分大于或等于后手得分，因此先手成为赢家，否则后手成为赢家。
public static boolean PredictTheWinner4(int[] nums) {
int len = nums.length;
int[][] dp = new int[len][len];
for(int i = 0; i < len; i++) {
dp[i][i] = nums[i];
}
for(int i = len - 2; i >= 0; i--) {
for(int j = i + 1; j < len; j++) {
dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][len - 1] >= 0;
}
方法六：动态规划优化
分析
上述代码中使用了二维数组 dp \textit{dp} dp。分析状态转移方程可以看到， dp [ i ] [ j \textit{dp}[i][j dp[i][j 的值只和 dp [ i + 1 ] [ j ] \textit{dp}[i + 1][j] dp[i+1][j]与 dp [ i ] [ j − 1 ] \textit{dp}[i][j - 1] dp[i][j−1]有关，即在计算 dp \textit{dp} dp的第 ii 行的值时，只需要使用到 dp \textit{dp} dp的第 i 行和第 i+1 行的值，因此可以使用一维数组代替二维数组，对空间进行优化。
public static boolean PredictTheWinner5(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
for(int i = 0; i < len; i++) {
dp[i] = nums[i];
}
for(int i = len - 2; i >= 0; i--) {
for(int j = i + 1; j < len; j++) {
dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
}
}
return dp[len - 1] >= 0;
}
