当前位置：首页 > article >正文

Leetcode 486. 预测赢家

article 2024/10/11 21:59:49

在这里插入图片描述

1、心路历程

这道题最开始想到的做法是回溯，因为看起来遍历就可以做，但是又想到同时需要维护两个人的数据就有点懵了。后来提示说用动态规划做是OK的。

这道题最难的地方在于，需要把输赢建模成“净胜分”，这样就能把两个主体合并为一个主体去动态规划。在明白了这一点之后，5分钟就自己写出来了。

这道题的本质和hot100里那个乘积最大子数组需要区分正负数一样，这里也需要区分两个人来分别递推。

2、注意的点

1、注意当递推到第二个人手里时，需要求得是一个最小值而不是最大值。

3、解法递归动态规划：

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        @cache
        def dp(i, j, k): # i - j 区间的最大净胜值 k = 1代表先手者 否则是后手者
            if j - i == 0:
                if k == 1:
                    return nums[i]
                else:
                    return - nums[i]
            if k == 1:
                return max(nums[i] + dp(i+1, j, 0), nums[j] + dp(i, j-1, 0))
            else:
                return min(-nums[i] + dp(i+1, j, 1), - nums[j] + dp(i, j-1, 1))
        return dp(0, n-1, 1) >= 0