486. 预测赢家

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        /**
        动态规划
            dp[i][j]: 当前玩家在数组[i:j]中先手，当前玩家所赢过对方的分数。
         */
         int n=nums.length;
         int[][] dp=new int[n][n];
         for(int i=0;i<n;i++){
             dp[i][i]=nums[i];//对角线上的 在i,i中选择  只能选择num[i]
         }
         for(int i=n-2;i>=0;i--){
             for(int j=i+1;j<n;j++){
                 //选择开头i 那么另一选择 [i+1,j]
                  //选择结尾j 那么另一选择 [i,j-1]
                 dp[i][j]=Math.max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]);
             }
         }
         return dp[0][n-1]>=0;//当前玩家在数组[i:j]中先手，当前玩家所赢过对方的分数。
    }
}