区间型动态规划——预测赢家

女爷i 2022-10-27 12:06 162阅读 0赞

#  #

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 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 。

### 1、题目分析 ###

这道题是一道博弈题，目标就是使得自己拿到的数字之和不比对手的小呢。但是为什么不放在博弈类型的动态规划中解决，是因为这个题目有一个题眼。那就是从数组的任意一端拿去一个分数，这个描述使得题目也是一道区间类的动态规划。

假设玩家1的分数之和是A，玩家2是B，即目标是A>=B，等价于A-B>=0。

也就是说，如果玩家1和玩家2都存着自己的数字和与对手的数字和之差， 分别记为SA =A-B， SB =B-A。则玩家1的目标是最大化SA，玩家2的目标是最大化SB。

当一方玩家1面对剩下的数字，可以认为玩家1就是当前的先手，他的目标就是最大化SA =A-B

当他取走一个数字m后，玩家2变成先手，同理他也要最大化SB =B-A

对于玩家1来说，SA = -SB + m

其中，m是当前这步的数字，-SB 是对手看来的数字差取相反数（因为先手是玩家1）

现在玩家1有两种选择，取第一个数字m1 或最后一个数字m2 ，为了最大化SA ， 应该选择较大的那个SA

### 2、确定状态 ###

如果玩家1第一步取走a\[0\]，玩家2面对a\[1…N-1\]

玩家2的最大数字差是SY

玩家1的数字差是a\[0\]-SY

如果玩家1第一步取走a\[N-1\]，玩家2面对a\[0…N-2\]

玩家2的最大数字差是S’Y

玩家1的数字差是a\[N-1\]-S’Y

玩家1选择较大的数字差

当玩家2面对a\[1…N-1\]，他这时是先手

他的目标同样是最大化先手（自己）和后手（玩家2）的数字差

但是此时的数字少了一个：a\[1…N-1\]

所以假设状态设f\[i\]\[j\]为一方先手在面对a\[i…j\]这些数字时，能得到的最大的与对手的数字差

### 3、转移方程 ###

假设状态设f\[i\]\[j\]为一方先手在面对a\[i…j\]这些数字时，能得到的最大的与对手的数字差

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

### 4、初始条件与边界情况 ###

只有一个数字a\[i\]时，己方得a\[i\]分，对手0分，数字差为a\[i\]

– f\[i\]\[i\] = a\[i\] (i=0, 1, …, N-1)

### 5、计算顺序 ###

遇上一个题目相同，同样会按照长度递增的顺序计算。

如果f\[0\]\[N-1\]>=0，先手玩家1必赢，否则必输

时间复杂度O(N\*N )，空间复杂度O(N\*N)

### 6、代码实现 ###

class Solution:
        def PredictTheWinner(self, nums: List[int]) -> bool:
            if len(nums)==0:
                return False
            n=len(nums)
            dp=[[0]*n for i in range(n)]
            for i in range(n):
                dp[i][i]=nums[i]
            for i in range(n-1,-1,-1):
                for j in range(i+1,n):
                    dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
            if dp[0][n-1]>=0:
                return True
            else:
                return False

#  #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/14a7b3710c46419fa336f6a639e7693e.png