预测赢家
给出一个非负整数的分数数组。玩家1从数组的任意一端（首尾）选择一个数字，然后是玩家2重复此操作，然后是玩家1，以此类推。每次玩家选择一个号码时，该号码将不能用于下一个玩家。这将持续到所有的分数被选择。得分最高的玩家获胜。
给定一组分数，预测玩家1是否获胜。你可以假设每个球员都是为了最大化自己的得分。
输入: [1, 5, 2]
输出: False
解释: 最初，玩家1可以选择1和2。
如果他选择2(或1)，那么玩家2可以选择1(或2)和5。如果玩家2选择5，那么玩家1将剩下1(或2)。
玩家1的最终得分是1 + 2 = 3，玩家2是5。
因此，玩家1永远不会是赢家，你需要返回False。
解析
这题和No. 877类似，假设我们需要知道nums[i:j]的玩家1的最大得分，那么显然它只取决于两种情况：玩家1选nums[i]，玩家2选剩下的最大；或者玩家1选nums[j]，玩家2选剩下的最大。考虑到玩家1,2都是从最利于自己的选择开始选的，那么玩家1和玩家2的选择策略是一样的，表现在公式上即是：dp[i][j]=max(nums[i]−dp[i+1][j],nums[j]−dp[i][j−1])。
Java代码
public boolean PredictTheWinner(int[] nums) {
int dp[][] = new int[nums.length+1][nums.length];
for(int i=nums.length-1;i>=0;i--){
for(int j=i+1;j<nums.length;j++){
dp[i][j] = Math.max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]);
}
}
return dp[0][nums.length-1]>=0;
}