↓Skip to main content
  1. Posts/

LeetCode-1690 石子游戏 VII

·1 min·
Table of Contents

LeetCode-1690 石子游戏 VII #

Solution 1 #

区间 dp.

代码如下:

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        s = list(accumulate(stones))
        n = len(stones)
        dp = [[-inf for _ in range(n)] for _ in range(n)]
        for l in range(n):
            for i in range(n - l):
                j = i + l
                if i == j:
                    dp[i][j] = 0
                else:
                    dp[i][j] = max(dp[i][j], max(s[j] - s[i] - dp[i + 1][j], s[j - 1] - (0 if i == 0 else s[i - 1]) - dp[i][j - 1]))
        return dp[0][n - 1]