0486. 预测赢家

ITCharge大约 3 分钟

0486. 预测赢家

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

题目链接

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$ 。

当 $i == j$ 时，当前玩家只能拿取 $nums[i]$ ，因此对于所有 $0 \le i < nums.length$ ，都有： $dp[i][i] = nums[i]$ 。
当 $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)$ 。