乐趣区

关于java:LeetCode–预测玩家

jiezi

LeetCode–预测玩家

<!– more –>

博客阐明

文章所波及的材料来自互联网整顿和集体总结，意在于集体学习和教训汇总，如有什么中央侵权，请分割自己删除，谢谢！

介绍

486. 预测赢家

题目

给定一个示意分数的非负整数数组。玩家 1 从数组任意一端拿取一个分数，随后玩家 2 持续从残余数组任意一端拿取分数，而后玩家 1 拿，……。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有残余分数可取时游戏完结。最终取得分数总和最多的玩家获胜。

给定一个示意分数的数组，预测玩家 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。
示例 2：
 输出：[1, 5, 233, 7]
输入：True
解释：玩家 1 一开始抉择 1。而后玩家 2 必须从 5 和 7 中进行抉择。无论玩家 2 抉择了哪个，玩家 1 都能够抉择 233。最终，玩家 1（234 分）比玩家 2（12 分）取得更多的分数，所以返回 True，示意玩家 1 能够成为赢家。
提醒：
1 <= 给定的数组长度 <= 20.
数组里所有分数都为非正数且不会大于 10000000。如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。

代码 

class Solution {public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        for(int i = 0;i < length; i++){dp[i] = nums[i];
        }
        for(int i = length - 2; i >= 0; i--){for(int j = i + 1; j < length; j++){
                // 记录以后玩家与其余玩家的差值
                dp[j] = Math.max(nums[i] - dp[j],nums[j] - dp[j-1]);
            }
        }
        // 返回最初的后果
        return dp[length - 1] >= 0;
    }
}

感激

Leetcode

以及勤奋的本人，集体博客，GitHub

退出移动版