思路
贪心策略不行，如果玩家每次都选相对自己当下可选择的最大值，这样的贪心策略有错误，比如这个例子：
输入：nums = [1,5,233,7]
输出：true
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。
java实现
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 = 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;
// if(turn == 1){
// return Math.max(scoreStart ,scoreEnd );
// }else{
// return Math.min(scoreStart ,scoreEnd );
// }
}
}
评论区