预测赢家

题目链接

题目原文 给定一个表示分数的非负整数数组。 玩家 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 仍为赢家。

题目解析

本题可以理解为一个博弈问题,即每次决策的差值最大化,让对方的收益最小,我们可以计算每次二者的差值,如果差值大于等于0,则玩家1获胜。这里仅讨论遍历解空间和动态规划的方法。

解题方法

递归

递归框架

首先,我们可以回顾一下递归算法的框架:

def recursion(start,end):#参数可以是当前节点,也可以是一个范围(回想递归实现的快排)
    #终止条件是递归的必须操作,在写递归算法之前一定要考虑清楚终止条件。
    if 终止条件 return
    # 进行选择
    recursion(start,mid)
    recursion(mid+1,end)

代码

对于本题,我们将问题化简为每一步该玩家的得分是正还是负,同时由于玩家1和2是轮流操作,因此,每一层的递归表示不同玩家的操作,需要一个参数来标志玩家。

由于,每次玩家可以从两端人选一个数,因此每一层有两种选择,将每层数组范围表示为(start,end),该层玩家可以选择start 或者 end,到下一层时,另一名玩家只能选择(start+1,end) 或这 (start,end-1) 范围的分数。

当只剩下一个数字时,玩家没有其他选择,并且此时游戏结束,因此,递归的终止条件应该为该层递归的输入start=end,返回对应的分数。

观察下图,玩家1的分数为正,玩家2的分数为负,同时,因为玩家1和玩家2存在博弈,均希望自己的每一次选择的收益最大化,以第三层玩家1为例,在每一次选择时,都期望得分最大。因为,玩家2的分数为负,自然需要取最小值。

递归解空间递归解空间

写递归时候有一个小技巧,先填写终止条件,之后考虑最后一个子空间的情况。

下面给出代码,可直接复制到leetcode运行:

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        #递归,增加参数turn,用来标记玩家1和2
        def total(start,end,turn):
            #终止条件
            if start==end:
                #返回该玩家的分数
                return nums[start]*turn
            #进行选择,每层玩家可以选择两端
            scoreStart=nums[start]*turn+ total(start+1,end,-turn)
            scoreEnd=nums[end]*turn+total(start,end-1,-turn)
            #返回该层选择后的最优值
            if turn==1: #玩家1的选择,因为分数为正,返回最大值
                return max(scoreStart,scoreEnd)
            else: #玩家2的选择,因为分数为负,返回最小值
                return min(scoreStart,scoreEnd)
        return total(0,len(nums)-1,1) >= 0

复杂度分析

  • 时间复杂度 O(2^n),n是数组长度
    这里有一个降低复杂度的方法,如果数组为偶数,那么先手必赢。
    图解图解

    从图中可以看出,偶数情况下,先手可以选择两组中的任意组,所以只需要计算两组的大小,先手必定取得胜利。
    因此改进算法如下:
class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        #递归,增加参数turn,用来标记玩家1和2
        def total(start,end,turn):
            #终止条件
            if start==end:
                #返回该玩家的分数
                return nums[start]*turn
            #进行选择,每层玩家可以选择两端
            scoreStart=nums[start]*turn+ total(start+1,end,-turn)
            scoreEnd=nums[end]*turn+total(start,end-1,-turn)
            #返回该层选择后的最优值
            if turn==1: #玩家1的选择,因为分数为正,返回最大值
                return max(scoreStart*turn , scoreEnd*turn)
            else: #玩家2的选择,因为分数为负,返回最小值
                return min(scoreStart * turn,scoreEnd *turn)
        if len(nums)%2==0:
            return True        
        return total(0,len(nums)-1,1) >= 0 

动态规划

问题分析

动态规划算法主要目标是填充二维数组dp,分析状态转移方程。
这里,我们定义二维数组dp,他的行列数都等于数组长度,dp[i][j]表示当数组剩下(i,j)时,当前玩家与另一个玩家分数之差的最大值。
此时,只有i<=j时,数组才有意义,因此只填写i<=j的部分。
当i==j时,同刚刚讨论的终止条件,dp[i][i]=nums[i]dp[i][i]=nums[i]
i<ji < j 时,玩家可以选择num[i]num[i]或者num[j]num[j],那么剩下的最优选择出现在dp[i+1][j]dp[i+1][j](i+1,j)里或者dp[i,j1]dp[i,j-1](i,j-1)里。
因此可以得到如下状态转移方程:
dp[i][j]=max(nums[i]dp[i+1][j],nums[j]dp[i][j1])(1) dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]) \tag{1}

总结

小心使用递归,复杂度很大的情况下,性能可能极差,造成超时。使用动态规划时,需要仔细分析可以直接填充的点,进而利用状态转移方程求解问题。

参考

leetcode题解