What is the main pattern in Stone Game VIII?

State transition dynamic programming using prefix sums is the key pattern to compute optimal score difference.

Can Stone Game VIII be solved without prefix sums?

Technically yes, but recomputing sums repeatedly would be inefficient and likely cause TLE for large n.

Why must at least two stones be removed each turn?

This rule ensures the new stone value is meaningful and prevents trivial moves that break the DP recurrence.

What is the optimal way to track DP states?

Maintain dp[i] representing the maximum difference after removing i stones, updating with dp[i] = max(dp[i-1], prefixSum[i] - dp[i-1]).

How does GhostInterview assist for this problem?

It guides solving Stone Game VIII by enforcing correct DP state updates, prefix sum usage, and avoiding common calculation pitfalls.

#1872

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

石子游戏 VIII

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手。总共有 n 个石子排成一行。轮到某个玩家的回合时，如果石子的数目大于 1 ，他将执行以下操作：选择一个整数 x > 1 ，并且移除最左边的 x 个石子。将移除的石子价值之和累加到该玩家的分数中。将一个新的…

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

题目描述

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手 。

总共有 n 个石子排成一行。轮到某个玩家的回合时，如果石子的数目 大于 1 ，他将执行以下操作：

选择一个整数 x > 1 ，并且移除最左边的 x 个石子。
将移除的石子价值之和累加到该玩家的分数中。
将一个 新的石子 放在最左边，且新石子的值为被移除石子值之和。

当只剩下一个石子时，游戏结束。

Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差，Bob 的目标是 最小化 分数差。

给你一个长度为 n 的整数数组 stones ，其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用最优策略的情况下，Alice 和 Bob 的 分数之差 。

示例 1：

输入：stones = [-1,2,-3,4,-5]
输出：5
解释：
- Alice 移除最左边的 4 个石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。
- Bob 移除最左边的 2 个石子，得分增加 2 + (-5) = -3 ，并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。
两者分数之差为 2 - (-3) = 5 。

示例 2：

输入：stones = [7,-6,5,10,5,-2,-6]
输出：13
解释：
- Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，并且将一个价值为 13 的石子放在最左边。stones = [13] 。
两者分数之差为 13 - 0 = 13 。

示例 3：

输入：stones = [-10,-12]
输出：-22
解释：
- Alice 只有一种操作，就是移除所有石子。得分增加 (-10) + (-12) = -22 ，并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。
两者分数之差为 (-22) - 0 = -22 。

提示：

n == stones.length
2 <= n <= 10⁵
-10⁴ <= stones[i] <= 10⁴

lightbulb

解题思路

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

根据题目描述，每次取走最左边的 $x$ 个石子，把它们的和加到自己的分数中，然后把一个价值为这个和的石子放在最左边，相当于把这 $x$ 个石子合并成了一个价值为这个和的石子，前缀和不变。

我们可以用一个长度为 $n$ 的前缀和数组 $s$ 来表示数组 $stones$ 的前缀和，其中 $s[i]$ 表示 $stones[0..i]$ 的元素和。

接下来，我们设计一个函数 $dfs(i)$ ，表示当前从 $stones[i:]$ 中取石子，返回当前玩家能得到的最大分数差。

函数 $dfs(i)$ 的执行过程如下：

如果 $i \geq n - 1$ ，说明当前只能取走全部石子，因此返回 $s[n - 1]$ 。
否则，我们可以选择从 $stones[i + 1:]$ 中取走全部石子，得到的分数差为 $dfs(i + 1)$ ；也可以选择取走 $stones[:i]$ 的石子，得到的分数差为 $s[i] - dfs(i + 1)$ 。我们取两种情况中的最大值，即为当前玩家能得到的最大分数差。

最终，我们可以得到 Alice 和 Bob 的分数之差为 $dfs(1)$ ，即 $Alice$ 必须从 $stones[1:]$ 中取石子开始游戏。

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

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

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(stones) - 1:
                return s[-1]
            return max(dfs(i + 1), s[i] - dfs(i + 1))

        s = list(accumulate(stones))
        return dfs(1)

speed

复杂度分析

指标	值
时间	complexity is O(n) due to single pass DP using prefix sums. Space complexity is O(n) if storing full DP array or O(1) if optimized to keep only previous state.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expecting prefix sum usage for move sums
question_mark
Checking understanding of state transition DP
question_mark
Looking for handling large n efficiently without nested loops

warning

常见陷阱

外企场景

error
Ignoring that at least two stones must be removed per move
error
Incorrectly tracking score difference instead of individual scores
error
Recomputing prefix sums in inner loops causing TLE

swap_horiz

进阶变体

外企场景

arrow_right_alt
Changing score function to product instead of sum
arrow_right_alt
Allowing removal of exactly k stones instead of at least two
arrow_right_alt
Scoring based on alternating stone positions rather than prefix sums

help

常见问题

外企场景

继续练习

#1140 石子游戏 II #1728 猫和老鼠 II #1690 石子游戏 VII