LeetCode-877 石子游戏

Table of Contents

LeetCode-877 石子游戏 #

Solution 1 #

$dp[l, r]$ 代表从 $nums[l:r+1]$ 开始选, 先手与后手的最大分差. 那么有 $$ dp[l, r] = \begin{cases} nums[l], l==r\ \max(nums[l] - dp[l + 1, r], nums[r] - dp[l, r - 1]) \end{cases} $$

代码如下:

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @cache
        def f(l, r):
            return piles[l] if l == r else max(piles[l] - f(l + 1, r), piles[r] - f(l, r - 1))
        return f(0, len(piles) - 1) > 0

Solution 2 #

由于总堆数为偶数, 因此先手可以保证自己取走全奇数下标的石子堆或全偶数下标的石子堆, 故有必胜策略.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True