1140：石子游戏 II（2034 分）

力扣第 147 场周赛第 4 题

题目

爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。

示例 1：

输入：piles = [2,7,9,4,4]
输出：10
解释：如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。

示例 2:

输入：piles = [1,2,3,4,5,100]
输出：104

提示：

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 104

相似问题：

• 1563：石子游戏 V（2087 分）
• 1686：石子游戏 VI（2000 分）
• 1690：石子游戏 VII（1951 分）
• 1872：石子游戏 VIII（2439 分）
• 2029：石子游戏 IX（2277 分）

分析

典型的博弈问题，多加一个 M 参数即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @cache
        def dfs(i,m):
            res = sum(piles[i:])
            if i+2*m<n:
                res -= min(dfs(i+x,max(x,m)) for x in range(1,2*m+1))
            return res
        n = len(piles)
        return dfs(0,1)

146 ms