https://leetcode.com/problems/predict-the-winner/description/
486. Predict the Winner
給定一個陣列 nums ， nums[i] 表示第 i 個物品的分數，有兩個玩家AB輪流從
nums 的最左或最右元素裡面取一個元素並得到該分數，若A和B的每一步都是最
聰明的選擇，返回A先選的情況是否分數總是比B大（相等的情況仍是A贏）。
Example 1:
Input: nums = [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: nums = [1,5,233,7]
Output: true
Explanation: Player 1 first chooses 1. Then player 2 has 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.
思路：
1.選和不選的問題基本上都是動態規劃問題，所以先從遞迴方式來考慮解決此問題。
2.當 nums 長度為1的時候，很明顯最佳的選擇就是唯一的元素
當 nums 長度為2的時候，很明顯最佳選則會是 MAX(nums[0], nums[1])
當 nums 長度為3的時候，最佳選擇可以分成拿左和拿右
拿左的最佳選擇：nums[0] - 玩家二在 nums[1~2] 可獲得的最大分數
拿右的最佳選擇：nums[2] - 玩家二在 nums[0~1] 可獲得的最大分數
上面兩個選擇取較大的就是長度3的最佳分數
當 nums 大於 3 的時候繼續推導，不失一般性。
3.有遞迴關係式之後就可以寫成 dfs 形式了，其中陣列 [i,j] 之間可獲得的最大分數
會重複遞迴好幾次，所以可以用一個 memo 去紀錄（DP）。
4.最後判斷返回值是否大於0就好。
Java Code：