算法刷题打卡第32天：预测赢家---动态规划

预测赢家

难度：中等
给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

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

如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 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 。
1
2
3
4
5
6
7
8

示例 2：

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

解法一、动态规划：二维数组

思路：
方法一使用递归，存在大量重复计算，因此时间复杂度很高。由于存在重复子问题，因此可以使用动态规划降低时间复杂度。

定义二维数组 $\text{dp}$，其行数和列数都等于数组的长度，$\text{dp}[i][j]$ 表示当数组剩下的部分为下标 $i$ 到下标 $j$ 时，即在下标范围 $[i,j]$ 中，当前玩家与另一个玩家的分数之差的最大值，注意当前玩家不一定是先手。

• 只有当 $i\le j$ 时，数组剩下的部分才有意义，因此当 $i>j$ 时，$\text{dp}[i][j]=0$。

• 当 $i=j$ 时，只剩一个数字，当前玩家只能拿取这个数字，因此对于所有 $0\le i<\text{nums}.\text{length}$，都有 $\text{dp}[i][i]=\text{nums}[i]$。

• 当 $i<j$ 时，当前玩家可以选择 $\text{nums}[i]$ 或 $\text{nums}[j]$，然后轮到另一个玩家在数组剩下的部分选取数字。在两种方案中，当前玩家会选择最优的方案，使得自己的分数最大化。因此可以得到如下状态转移方程：

  • $\text{dp}[i][j]=\max (\text{nums}[i]-\text{dp}[i+1][j],\text{nums}[j]-\text{dp}[i][j-1])$

最后判断 $\text{dp}[0][\text{nums}.\text{length}-1]$ 的值，如果大于或等于 $0$，则先手得分大于或等于后手得分，因此先手成为赢家，否则后手成为赢家。

时间复杂度：$O(n^2)$，其中 $n$ 是数组的长度。需要计算每个子数组对应的 $\text{dp}$ 的值，共有 $\frac{n(n+1)}{2}$ 个子数组。
空间复杂度：$O(n^2)$，其中 $n$ 是数组的长度。空间复杂度取决于额外创建的数组 $\text{dp}$。

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        length = len(nums)
        dp = [[nums[i] if i == j else 0 for i in range(length)] for j in range(length)]
        for i in range(length-2, -1, -1):
            for j in range(i+1, length):
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
        return dp[0][length-1] >= 0
1
2
3
4
5
6
7
8

解法二、动态规划：一维数组

思路：
上述代码中使用了二维数组 $\text{dp}$。分析状态转移方程可以看到，$\text{dp}[i][j]$ 的值只和 $\text{dp}[i+1][j]$ 与 $\text{dp}[i][j-1]$ 有关，即在计算 $\text{dp}$ 的第 $i$ 行的值时，只需要使用到 $\text{dp}$ 的第 $i$ 行和第 $i+1$ 行的值，因此可以使用一维数组代替二维数组，对空间进行优化。

时间复杂度：$O(n^2)$，其中 $n$ 是数组的长度。需要计算每个子数组对应的 $\text{dp}$ 的值，共有 $\frac{n(n+1)}{2}$ 个子数组。
空间复杂度：$O(n)$，其中 $n$ 是数组的长度。空间复杂度取决于额外创建的数组 $\text{dp}$。

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        length = len(nums)
        dp = nums.copy()
        for i in range(length-2, -1, -1):
            for j in range(i+1, length):
            	# 因为每次使用的都是当次替换前的值和上次替换过的值
            	# 所以直接进行覆盖不会影响最终结果
                dp[j] = max(nums[i] - dp[j], nums[j] - dp[j-1])
        return dp[length-1] >= 0
1
2
3
4
5
6
7
8
9
10

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/predict-the-winner