算法刷题打卡第31天：预测赢家---递归

预测赢家

难度：中等
给你一个整数数组 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

解法一、递归：计算先手最大分数

思路：
为了判断哪个玩家可以获胜，需要计算一个总分，即先手能得到的最高分数。当数组中的所有数字都被拿取时，后手分数则为全部总分减去先手总分，进而判断先手是否大于后手。大于则先手获胜，反之则后手获胜。

由于每次只能从数组的任意一端拿取数字，因此可以保证数组中剩下的部分一定是连续的。假设每次先手都按照最好的结果去取数字，后手也是如此，那么后手每次都会留给先手最差的选择，则可以推导得到递归的等式为：

• $l\_score=nums[left]+min(maxscore(left+2,right),maxscore(left+1,right-1))$
• $r\_score=nums[right]+min(maxscore(left+1,right-1),maxscore(left,right-2))$

其中 $l\_score$ 和 $r\_score$ 分别为拿左拿右的最大总分。

时间复杂度： $O(2^n)$，其中 $n$ 是数组的长度。
空间复杂度： $O(n)$，其中 $n$ 是数组的长度。空间复杂度取决于递归使用的栈空间。

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        def maxscore(left, right):
            if left == right:
                return nums[left]
            elif right - left == 1:
                l_score = nums[left]
                r_score = nums[right]
            else:
            	# 避免单次递归中出现重复递归
                mid_score = maxscore(left+1, right-1)
                l_score = nums[left] + min(maxscore(left+2, right), mid_score)
                r_score = nums[right] + min(mid_score, maxscore(left, right-2))
            return max(l_score, r_score)
        score = maxscore(0, len(nums)-1)
        return score >= sum(nums)-score
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解法二、递归：计算先手最大超过分数

思路：
为了判断哪个玩家可以获胜，需要计算一个总分，即先手得分与后手得分之差。当数组中的所有数字都被拿取时，如果总分大于或等于 $0$，则先手获胜，反之则后手获胜。

由于每次只能从数组的任意一端拿取数字，因此可以保证数组中剩下的部分一定是连续的。假设数组当前剩下的部分为下标 $\text{left}$ 到下标 $\text{right}$，其中 $0\le \text{start}\le \text{end}<\text{nums}.\text{length}$。如果 $\text{start}=\text{end}$，则只剩一个数字，当前玩家只能拿取这个数字。如果 $\text{left}<\text{right}$，则当前玩家可以选择 $\text{nums}[\text{left}]$ 或 $\text{nums}[\text{right}]$，然后轮到另一个玩家在数组剩下的部分选取数字。这是一个递归的过程。

时间复杂度： $O(2^n)$，其中 $n$ 是数组的长度。
空间复杂度： $O(n)$，其中 $n$ 是数组的长度。空间复杂度取决于递归使用的栈空间。

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        def max_difference(left, right):
            if left == right:
                return nums[left]
            l_diff = nums[left] - max_difference(left+1, right)
            r_diff = nums[right] - max_difference(left, right-1)
            return max(l_diff, r_diff)
        return max_difference(0, len(nums)-1) >= 0
1
2
3
4
5
6
7
8
9

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