给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数
    组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可
    取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
    给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最
    大化。
    两个值的时候必然是取较大的，三个值，取一个能使自己分数和最大的，后手必然留较小的给先手，因
    此先手选一个值加上该较小值最大化

    1. static int maxScore(int[] nums, int l, int r) {
    2.     //剩下一个值，只能取该值 
    3.     if (l == r) {
    4.         return nums[l];
    5.     }
    7.     int selectLeft = 0;
    8.     int selectRight = nums.length - 1;
    10.     //剩下大于两个值，先手选一边(使自己得分最高的一边)，后手则选使对手得分最低的一边 
    11.     if ((r - l) >= 2) {
    12.         selectLeft = nums[l] +
    13.             Math.min(maxScore(nums, l + 2, r), maxScore(nums, l + 1, r - 1));
    14.         selectRight = nums[r] +
    15.             Math.min(maxScore(nums, l + 1, r - 1), maxScore(nums, l, r - 2));
    16.     }
    18.     //剩下两个值，取较大的 
    19.     if ((r - l) == 1) {
    20.         selectLeft = nums[l];
    21.         selectRight = nums[r];
    22.     }
    24.     return Math.max(selectLeft, selectRight);
    25. }
    27. int getScore(int[] nums, int start, int end) {
    28.     int selectLeft;
    29.     int selectRight;
    30.     int gap = end - start;
    32.     if (gap == 0) {
    33.         return nums[start];
    34.     } else if (gap == 1) {
    35.         // 此时直接取左右的值就可以 
    36.         selectLeft = nums[start];
    37.         selectRight = nums[end];
    38.     } else if (gap >= 2) {
    39.         // 如果gap大于2，递归计算selectLeft和selectRight 
    40.         // 计算的过程为什么用min，因为要按照对手也是最聪明的来计算。 
    41.         int num = getScore(nums, start + 1, end - 1);
    42.         selectLeft = nums[start] +
    43.             min(getScore(nums, start + 2, end), num);
    44.         selectRight = nums[end] + min(num, getScore(nums, start, end - 2));
    45.     }
    47.     return max(selectLeft, selectRight);
    48. }
    50. bool PredictTheWinner(int[] nums) {
    51.     int sum = 0;
    53.     for (int i : nums) {
    54.         sum += i;
    55.     }
    57.     int player1 = getScore(nums, 0, nums.size() - 1);
    58.     int player2 = sum - player1;
    60.     // 如果最终两个玩家的分数相等，那么玩家 1 仍为赢家，所以是大于等于。
    61.     return player1 >= player2;
    63.     //return getScore(nums, 0, nums.size() - 1) >=0 ;
    64. }
    66. //差值
    67. int getScore(int[] nums, int start, int end) {
    68.     if (end == start) {
    69.         return nums[start];
    70.     }
    72.     int selectLeft = nums[start] - getScore(nums, start + 1, end);
    73.     int selectRight = nums[end] - getScore(nums, start, end - 1);
    75.     return max(selectLeft, selectRight);
    76. }

    动态规划：使用二维数组存储差值

    1. public boolean PredictTheWinner(int[] nums) {
    2.     int length = nums.length;
    3.     int[][] dp = new int[length][length];
    5.     for (int i = 0; i < length; i++) {
    6.         dp[i][i] = nums[i];
    7.     }
    9.     for (int i = length - 2; i >= 0; i--) {
    10.         for (int j = i + 1; j < length; j++) {
    11.             //j = i +1 因此可以优化为一维数组,下标位置相同才有值，据此推导其他的值 
    12.             //Math.max(nums[i] - dp[j][j], nums[j] - dp[j - 1][j - 1]); 
    13.             dp[i][j] = Math.max(nums[i] - dp[i + 1][j],
    14.                                 nums[j] - dp[i][j - 1]);
    15.         }
    16.     }
    18.     return dp[0][length - 1] >= 0;
    19. }