leetcode-486. 预测赢家

本文主要是介绍leetcode-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 仍为赢家。

解题思路

好几天不刷题，菜哦！递归也是看了官方题解做的

递归版
Use f(nums) to denote the maximum score, because player1 and player2 are competitors, every time the score is negative to another player. If the score >= 0, then player1 wins.

So the formula is: f(nums) = max(nums[0] - f(nums[1:]), nums[-1] - f(nums[:-1])

Time complexity: $o(2^n)$

dp版
看了题解做的，太聪明了靠……

用dp[i][j]表示数组从i到j这一段的得分，则i < j，所以dp是一个上三角矩阵。初始化的时候，dp[i][i] = nums[i]，正的，也即先手的人得到的分

那么之后每次的得分，其实都是在当前得分 - 对家的分后求个最大值，也即：
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]

最后看dp[0][len(nums) - 1]是否>=0

对于这种dp[i][j]依赖dp[i + 1][j], dp[i][j - 1]的题目，还可以把二维空间缩减到一维

代码

递归版

class Solution:def predictTheWinner(self, nums: List[int]) -> bool:def helper(nums: list) -> int:if len(nums) == 1:return nums[0]return max(nums[0] - helper(nums[1:]), nums[-1] - helper(nums[:-1]))return helper(nums) >= 0

Space Saver Version:

class Solution:def predictTheWinner(self, nums: List[int]) -> bool:memo = {}def helper(left: int, right: int, turn: int) -> int:if (left, right, turn) in memo:return memo[(left, right, turn)]if left > right:memo[(left, right, turn)] = 0return memo[(left, right, turn)]if turn == 1:res = max(nums[left] + helper(left + 1, right, 2), nums[right] + helper(left, right - 1, 2))memo[(left, right, turn)] = reselse:res = min(-nums[left] + helper(left + 1, right, 1), -nums[right] + helper(left, right - 1, 1))memo[(left, right, turn)] = resreturn memo[(left, right, turn)]return helper(0, len(nums) - 1, 1) >= 0

dp版

class Solution:def predictTheWinner(self, nums: List[int]) -> bool:dp = [[0] * len(nums) for _ in range(len(nums))]for i in range(len(nums) - 1, -1, -1):for j in range(i, len(nums)):if i == j:dp[i][j] = nums[i]else:dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])return dp[0][len(nums) - 1] >= 0

dp空间改进版

class Solution:def PredictTheWinner(self, nums: List[int]) -> bool:dp = nums[:]for row in range(len(nums) - 2, -1, -1):for col in range(row + 1, len(nums)):dp[col] = max(nums[col] - dp[col - 1], nums[row] - dp[col])return dp[len(nums) - 1] >= 0

这篇关于leetcode-486. 预测赢家的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---