LeetCode笔记：486. Predict the Winner

问题：

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins. Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score. Example 1: Input: [1, 5, 2] Output: False Explanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence, player 1 will never be the winner and you need to return False. Example 2: Input: [1, 5, 233, 7] Output: True Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233. Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win. Note:

1. 1 <= length of the array <= 20.
2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
3. If the scores of both players are equal, then player 1 is still the winner.

大意：

给出一个非负整数数组表示分数。玩家1从数组的第一个或者最后一个分数选择一个，接着玩家2在剩下的分数里继续这样选择，然后又玩家1选择，如此往复。每次由一个玩家选择，选择的数字下一个玩家不能再选。直到所有元素都被选择完。总分数更大的玩家获胜。 给出分数数组，预测玩家1是否是赢家。你可以假设每个玩家都尽量扩大他的分数。 例1： 输入：[1, 5, 2] 输出：False 解释：一开始，玩家1可以选择1或者2。 如果他选择2（或者1），玩家2可以选择1（或者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. 1 <= 数组的长度 <= 20。
2. 给出的数组中所有数字都是非负整数，而且不会超过10000000。
3. 如果两个玩家的分数相同，还是判玩家1胜。

思路：

这个如果要穷举所有可能的选法实在是太多了，而且也不是贪心算法，每次都取当前最大值，因为要考虑极大数的位置，比如例2的233。因此我们只能用递归来做。

假设所有分数的总和为sum，那么最后一定是玩家1选择了一部分，玩家2选择了另一部分，我们只需要玩家1的分数大于等于玩家2就可以了，那么可以想象成，每次玩家1选择一个分数，就是加一个分数，轮到玩家2选择时，就是减去一个分数，判断最后剩下的数字的正负就可以知道玩家1是否赢了。

我们另外创建一个函数，用来递归计算每次的加分数和减分数，最终值的正负就是赢与否，注意题目说分数相等也是玩家1赢，所以最后如果等于0，也是玩家1赢。

他山之石（Java）：

public class Solution {
    public boolean PredictTheWinner(int[] nums) {
        return findAns(nums, 0, nums.length-1) >= 0;
    }
    
    public int findAns(int[] nums, int i, int j) {
        if (i == j) return nums[i];
        else {
            int first = nums[i] - findAns(nums, i+1, j);
            int last = nums[j] - findAns(nums, i, j-1);
            return Math.max(first, last);
        }
    }
}

合集：https://github.com/Cloudox/LeetCode-Record