给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
示例 1：
1
2
3
4
5
6
| 输入：[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
2
3
4
| 输入：[1, 5, 233, 7]
输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。
|
提示：
- 1 <= 给定的数组长度 <= 20.
- 数组里所有分数都为非负数且不会大于 10000000 。
- 如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。
方法一：递归
为了判断哪个玩家可以获胜，我们计算一个总分，为先手和后手得分之差。当数组中所有数字被拿取时，如果总分大于等于 0，则先手获胜，反之则后手获胜。
每次可以从数组头和数组尾拿取一个数字，然后轮到另一个玩家在剩下的部分选取数字。计算总分时，需要记录当前玩家是先手还是后手，判断当前玩家的 得分应该记为正还是负。当数组中剩下的数字多于一个时，当前玩家会选择最优的方案，使自己的分数最大化，因此对两种方案分别计算当前玩家可以得到的分数，其中的最大值为当前玩家最多可以得到的分数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
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 = total(nums, start + 1, end, -turn) + nums[start] * turn;
int scoreEnd = total(nums, start, end - 1, -turn) + nums[end] * turn;
return Math.max(scoreStart * turn, scoreEnd * turn) * turn;
}
}
|
时间复杂度O(2^n)，n 是数组的长度。
空间复杂度O(n)，n 是数组的长度。
方法二：动态规划
定义二维数组 dp，其行数和列数都等于数组的长度，dp[i][j] 表示当前数组剩下的部分为下标 i 到下标 j时，当前玩家与另一个玩家的分数只差的最大值，注意当前玩家不一定是先手。
只有当 i <= j 时才有意义，当 i = j 时，只剩一个数字，当前玩家只能拿取这个数字，因此对于所有 0 <= i < nums.length，都有dp[i][i] = nums[i]。
当 i < j 时，当前玩家可以选择 nums[i] 或 nums[j]，然后轮到另一个玩家在数组剩下的部分选取数字。在两种方案中，当前玩家会选择最优的方案，使自己的分数最大化。得到转台方程：
$$
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
$$
nums[i] - dp[i + 1][j]代表选择数组头的元素减去另一个玩家的分数之差，nums[j] - dp[i][j - 1]代表选择数组尾的元素减去另一个玩家的分数之差。
最后判断 dp[0][nums.length - 1]的值，如果大于等于 0 则先手得分大于后手得分，先手赢，反之则后手赢。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public boolean PredictTheWinner(int[] nums) {
int length = nums.length;
int[][] dp = new int[length][length];
for(int i = 0; i < length; i++){
dp[i][i] = nums[i];
}
for(int i = length - 2; i >= 0; i--){
for(int j = i + 1; j < length; j++){
dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][length - 1] >= 0;
}
}
|
时间复杂度O(n^2)，n 是数组的长度。
空间复杂度O(n^2)，n 是数组的长度。
我们可以对空间复杂度进行优化.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public boolean PredictTheWinner(int[] nums) {
int length = nums.length;
int[] dp = new int[length];
for(int i = 0; i < length; i++){
dp[i] = nums[i];
}
for(int i = length - 2; i >= 0; i--){
for(int j = i + 1; j < length; j++){
dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
}
}
return dp[length - 1] >= 0;
}
}
|
时间复杂度O(n^2)，n 是数组的长度。
空间复杂度O(n)，n 是数组的长度。