乐趣区

关于java:LeetCode–预测玩家

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

退出移动版