Skip to content

Latest commit

 

History

History
99 lines (65 loc) · 3.73 KB

0486.md

File metadata and controls

99 lines (65 loc) · 3.73 KB

0486. 预测赢家

  • 标签：递归、数组、数学、动态规划、博弈
  • 难度：中等

题目链接

题目大意

描述：给定搞一个整数数组 $nums$。玩家 $1$ 和玩家 $2$ 基于这个数组设计了一个游戏。

玩家 $1$ 和玩家 $2$ 轮流进行自己的回合，玩家 $1$ 先手。

开始时，两个玩家的初始分值都是 $0$。每一回合，玩家从数组的任意一端取一个数字（即 $nums[0]$ 或 $nums[nums.length - 1]$），取到的数字将会从数组中移除（数组长度减 $1$）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

要求：如果玩家 $1$ 能成为赢家，则返回 True。否则返回 False。如果两个玩家得分相等，同样认为玩家 $1$ 是游戏的赢家，也返回 True。假设每个玩家的玩法都会使他的分数最大化。

说明：

  • $1 \le nums.length \le 20$。
  • $0 \le nums[i] \le 10^7$。

示例：

  • 示例 1：
输入：nums = [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：
输入：nums = [1,5,233,7]
输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。

解题思路

思路 1：动态规划

1. 划分阶段

按照区间长度进行阶段划分。

2. 定义状态

定义状态 $dp[i][j]$ 表示为：玩家 $1$ 与玩家 $2$ 在 $nums[i]...nums[j]$ 之间互相选取，玩家 $1$ 比玩家 $2$ 多的最大分数。

3. 状态转移方程

根据状态的定义，只有在 $i \le j$ 时才有意义，所以当 $i > j$ 时，$dp[i][j] = 0$。

  1. 当 $i == j$ 时，当前玩家只能拿取 $nums[i]$，因此对于所有 $0 \le i < nums.length$，都有：$dp[i][i] = nums[i]$。
  2. 当 $i < j$ 时，当前玩家可以选择 $nums[i]$ 或 $nums[j]$，并是自己的分数最大化，然后换另一位玩家从剩下部分选取数字。则转移方程为：$dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])$。
4. 初始条件
  • 当 $i > j$ 时，$dp[i][j] = 0$。
  • 当 $i == j$ 时，$dp[i][j] = nums[i]$。
5. 最终结果

根据我们之前定义的状态，$dp[i][j]$ 表示为：玩家 $1$ 与玩家 $2$ 在 $nums[i]...nums[j]$ 之间互相选取，玩家 $1$ 比玩家 $2$ 多的最大分数。则如果玩家 $1$ 想要赢，则 $dp[0][size - 1]$ 必须大于等于 $0$。所以最终结果为 $dp[0][size - 1] >= 0$。

思路 1：代码

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        size = len(nums)
        dp = [[0 for _ in range(size)] for _ in range(size)]

        for l in range(1, size + 1):
            for i in range(size):
                j = i + l - 1
                if j >= size:
                    break
                if l == 1:
                    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][size - 1] >= 0

思路 1：复杂度分析

  • 时间复杂度：$O(n^2)$。
  • 空间复杂度：$O(n^2)$。