# 486 Predict the Winner

題目給一正整數陣列，遊戲規則是player 1和player 2 輪流從數列的左右兩端選一數字，最後數字總和較大者勝利。假設player 1 和2都會用最聰明的方式選擇，問player 1贏的可能性是True還是False

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.

Concept 由於input為正整數陣列，直覺會想開二維dp，dp[i][j]表subarray(i,j)時，player 1的分數，接下來問題就是如何更新每個dp[i][j]。 當player 1在dp[i][j]選了一個數字後，要嘛是選i，要嘛是選j，選了i的話，subarray就變成(i+1, j)，選了j的話，subarray就變成(i, j-1)。但是！縮短後的subarray是輪到player2選，下次換player 1選又要再短一點了。因此可得： dp[i][j] = max(num[i] + min(dp[i+2][j], dp[i+1][j-1]), num[j] + min(dp[i+1][j-1], dp[i][j-2]))

中間是min的原因是，player 2 不會讓player 1選到大的。

最後結果會在dp[0][nums.length-1]這格。total - dp[0][nums.length-1] < dp[0][nums.length-1]就代表player 1贏了。

Code

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int total = 0;
        if(nums == null || nums.length == 0) return true;
        for(int num : nums) {
            total+=num;
        }
        int[][] dp = new int[nums.length][nums.length];
        for(int i=0;i<nums.length;i++) {
            for(int j=i;j>=0;--j) {
                if(i==j) {
                    dp[j][i] = nums[i];
                    continue;
                }
                if(i==j+1) {
                    dp[j][i] = Math.max(nums[j], nums[i]);
                    continue;
                }
                dp[j][i] = Math.max(nums[j] + Math.min(dp[j+2][i], dp[j+1][i-1]), 
                                    //player 2 will only let player 1 select the smaller number among (dp[j+2][i], dp[j+1][i-1])
                                    nums[i] + Math.min(dp[j+1][i-1], dp[j][i-2]));
            }
        }
        return !((total-dp[0][nums.length-1]) > dp[0][nums.length-1]);
    }
}