↓Skip to main content
  1. Posts/

LeetCode-1140 石子游戏 II

·1 min·
Table of Contents

LeetCode-1140 石子游戏 II #

Solution 1 #

$dp[i, m]$ 代表从 $i$ 开始取, $M=m$ 的先手最大得分, 递归.

代码如下:

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        for i in range(n - 1, -1, -1):
            piles[i] += (0 if i == n - 1 else piles[i + 1]) 

        @cache
        def f(i, m): # 先手最大得分
            if i == n:
                return 0 
            res = inf
            for x in range(1, 2 * m + 1):
                if i + x <= n:
                    res = min(res, f(i + x, max(m, x)))
            return piles[i] - res
            
        return f(0, 1)