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：