↓Skip to main content
  1. Posts/

LeetCode-1563 石子游戏 V

·1 min·
Table of Contents

LeetCode-1563 石子游戏 V #

Solution 1 #

区间 dp + 剪枝.

代码如下:

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)
        s = list(accumulate(stoneValue))
        @cache
        def f(l, r):
            if l == r:
                return 0
            res = 0
            for i in range(l, r):
                s_l = s[i] - (0 if l == 0 else s[l - 1])
                s_r = s[r] - s[i]
                if s_l > s_r and 2 * s_r > res:
                    res = max(res, s_r + f(i + 1, r))
                elif s_l == s_r and 2 * s_r > res:
                    res = max(res, max(s_l + f(l, i), s_r + f(i + 1, r)))
                elif s_l < s_r and 2 * s_l > res:
                    res = max(res, s_l + f(l, i))
            return res
        return f(0, n - 1)