What is the optimal strategy for Alice in the Stone Game II?

The optimal strategy involves using dynamic programming to track the maximum stones Alice can collect, considering the number of piles available at each step and the opponent’s responses.

How do I use dynamic programming to solve Stone Game II?

State transitions are tracked using dynamic programming, where each state is defined by the current pile index and the maximum number of piles that can be taken. This allows for efficient calculation of the best moves.

What does the state transition dynamic programming pattern mean for Stone Game II?

State transition dynamic programming means solving the problem by recursively determining the best choice at each state and transitioning between states based on the current conditions of the game.

Why is memoization crucial in Stone Game II?

Memoization is crucial because it ensures that previously computed results are reused, making the solution efficient by avoiding redundant calculations, especially for larger inputs.

Can I use a greedy approach to solve Stone Game II?

A greedy approach would not work because it doesn't account for future optimal decisions by the opponent. Dynamic programming is needed to optimize the overall game outcome considering both players' choices.

#1140

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

石子游戏 II

Alice 和 Bob 继续他们的石子游戏。许多堆石子排成一行，每堆都有正整数颗石子 piles[i] 。游戏以谁手中的石子最多来决出胜负。 Alice 和 Bob 轮流进行，Alice 先开始。最初， M = 1 。在每个玩家的回合中，该玩家可以拿走剩下的前 X 堆的所有石子，其中 1 。…

数组数学动态规划前缀和博弈论

题目描述

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

Alice 和 Bob 轮流进行，Alice 先开始。最初，M = 1。

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

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

假设 Alice 和 Bob 都发挥出最佳水平，返回 Alice 可以得到的最大数量的石头。

示例 1：

输入：piles = [2,7,9,4,4]
输出：10
解释：如果一开始 Alice 取了一堆，Bob 取了两堆，然后 Alice 再取两堆。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] <= 10⁴

lightbulb

解题思路

方法一：前缀和 + 记忆化搜索

由于玩家每次可以拿走前 $X$ 堆的所有石子，也就是说能拿走一个区间的石子，因此，我们可以先预处理出一个长度为 $n+1$ 的前缀和数组 $s$ ，其中 $s[i]$ 表示数组 piles 的前 $i$ 个元素的和。

然后我们设计一个函数 $dfs(i, m)$ ，表示当前轮到的人可以从数组 piles 的下标 $i$ 开始拿，且当前的 $M$ 为 $m$ 时，当前轮到的人能够拿到的最大石子数。初始时爱丽丝从下标 $0$ 开始，且 $M=1$ ，所以我们需要求的答案为 $dfs(0, 1)$ 。

函数 $dfs(i, m)$ 的计算过程如下：

如果当前轮到的人可以拿走剩下的所有石子，能够拿到的最大石子数为 $s[n] - s[i]$ ；
否则，当前轮到的人可以拿走剩下的前 $x$ 堆的所有石子，其中 $1 \leq x \leq 2m$ ，能够拿到的最大石子数为 $s[n] - s[i] - dfs(i + x, max(m, x))$ 。也即是说，当前轮的人能够拿到的石子数为当前剩下的所有石子数减去下一轮对手能够拿到的石子数。我们需要枚举所有的 $x$ ，取其中的最大值作为函数 $dfs(i, m)$ 的返回值。

为了避免重复计算，我们可以使用记忆化搜索。

最后，我们返回将 $dfs(0, 1)$ 作为答案返回即可。

时间复杂度为 $O(n^3)$ ，空间复杂度为 $O(n^2)$ 。其中 $n$ 为数组 piles 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

        n = len(piles)
        s = list(accumulate(piles, initial=0))
        return dfs(0, 1)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Assess the candidate’s understanding of dynamic programming and its application to game theory problems.
question_mark
Look for the ability to design a solution with efficient memoization to handle multiple states.
question_mark
Evaluate how well the candidate balances between recursion and optimization techniques for state transitions.

warning

常见陷阱

外企场景

error
Failing to correctly implement the state transition, which can result in incorrect results or inefficient solutions.
error
Overlooking the fact that the state space grows based on both the pile index and the maximum piles a player can take.
error
Not optimizing the solution with memoization, leading to excessive recomputation and poor performance on larger inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider modifying the game rules to allow players to take up to X piles, where X is a fixed number rather than based on M.
arrow_right_alt
Change the problem to allow players to skip turns, requiring a more complex state transition.
arrow_right_alt
Implement a variant where players can take stones from anywhere in the array rather than only starting from the first pile.

help

常见问题

外企场景

继续练习

#1728 猫和老鼠 II #486 预测赢家 #1248 统计「优美子数组」