LeetCode-1872 石子游戏 VIII

Table of Contents

LeetCode-1872 石子游戏 VIII #

Solution 1 #

问题等价于从前缀和数组 $s$ 中选值, 第一次选择从 $i=1,2,…$ 中选, 之后一名玩家选了 $i$ , 另一名要从 $i + 1, …, n - 1$ 中选. dp.

代码如下:

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        s = list(accumulate(stones))
        n = len(stones)
        @cache
        def f(i): 
            if i == n - 1:
                return s[n - 1]
            res = -inf
            res = max(f(i + 1), s[i] - f(i + 1))
            return res
        return f(1)