問題：

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.

大意：

給出一個非負整數(shù)數(shù)組表示分數(shù)。玩家1從數(shù)組的第一個或者最后一個分數(shù)選擇一個，接著玩家2在剩下的分數(shù)里繼續(xù)這樣選擇，然后又玩家1選擇，如此往復。每次由一個玩家選擇，選擇的數(shù)字下一個玩家不能再選。直到所有元素都被選擇完?？偡謹?shù)更大的玩家獲勝。
給出分數(shù)數(shù)組，預測玩家1是否是贏家。你可以假設每個玩家都盡量擴大他的分數(shù)。
例1：

輸入：[1, 5, 2]
輸出：False
解釋：一開始，玩家1可以選擇1或者2。
如果他選擇2（或者1），玩家2可以選擇1（或者2）和5，然后玩家1可以選剩下的1（或者2）。
所以，最后玩家1的分數(shù)是 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）的分數(shù)更高，所以你需要返回True代表玩家1贏。

注意：

1. 1 <= 數(shù)組的長度 <= 20。
2. 給出的數(shù)組中所有數(shù)字都是非負整數(shù)，而且不會超過10000000。
3. 如果兩個玩家的分數(shù)相同，還是判玩家1勝。

思路：

這個如果要窮舉所有可能的選法實在是太多了，而且也不是貪心算法，每次都取當前最大值，因為要考慮極大數(shù)的位置，比如例2的233。因此我們只能用遞歸來做。

假設所有分數(shù)的總和為sum，那么最后一定是玩家1選擇了一部分，玩家2選擇了另一部分，我們只需要玩家1的分數(shù)大于等于玩家2就可以了，那么可以想象成，每次玩家1選擇一個分數(shù)，就是加一個分數(shù)，輪到玩家2選擇時，就是減去一個分數(shù)，判斷最后剩下的數(shù)字的正負就可以知道玩家1是否贏了。

我們另外創(chuàng)建一個函數(shù)，用來遞歸計算每次的加分數(shù)和減分數(shù)，最終值的正負就是贏與否，注意題目說分數(shù)相等也是玩家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

查看作者首頁