What is the best approach for Stone Game VII?

Use state transition dynamic programming with prefix sums to compute maximum score difference efficiently.

Can Stone Game VII be solved using recursion alone?

Recursion without memoization is too slow; memoization or iterative DP is required for n up to 1000.

How are points calculated when removing a stone?

Points equal the sum of the remaining stones after removing either the leftmost or rightmost stone.

Why use prefix sums in Stone Game VII?

Prefix sums allow O(1) calculation of remaining subarray sums, avoiding repeated O(n) summations per move.

What common mistakes occur with state transition DP in this problem?

Misdefining dp[i][j] or failing to account for opponent's minimizing strategy often leads to incorrect maximum differences.

#1690

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

石子游戏 VII

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始。有 n 块石子排成一排。每个玩家的回合中，可以从行中移除最左边的石头或最右边的石头，并获得与该行中剩余石头值之和相等的得分。当没有石头可移除时，得分较高者获胜。鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力减…

数组数学动态规划博弈论

题目描述

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。

有 n 块石子排成一排。每个玩家的回合中，可以从行中移除最左边的石头或最右边的石头，并获得与该行中剩余石头值之和相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。

示例 1：

输入：stones = [5,3,1,4,2]
输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。

示例 2：

输入：stones = [7,90,5,1,100,10,10,2]
输出：122

提示：

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

lightbulb

解题思路

方法一：记忆化搜索

我们先预处理出前缀和数组 $s$ ，其中 $s[i]$ 表示前 $i$ 个石头的总和。

接下来，设计一个函数 $dfs(i, j)$ ，表示当剩下的石子为 $stones[i], stones[i + 1], \dots, stones[j]$ 时，先手与后手的得分差值。那么答案即为 $dfs(0, n - 1)$ 。

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

如果 $i \gt j$ ，说明当前没有石子，返回 $0$ ；
否则，先手有两种选择，分别是移除 $stones[i]$ 或 $stones[j]$ ，然后计算得分差值，即 $a = s[j + 1] - s[i + 1] - dfs(i + 1, j)$ 和 $b = s[j] - s[i] - dfs(i, j - 1)$ ，我们取两者中的较大值作为 $dfs(i, j)$ 的返回值。

过程中，我们使用记忆化搜索，即使用数组 $f$ 记录函数 $dfs(i, j)$ 的返回值，避免重复计算。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为石子的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i > j:
                return 0
            a = s[j + 1] - s[i + 1] - dfs(i + 1, j)
            b = s[j] - s[i] - dfs(i, j - 1)
            return max(a, b)

        s = list(accumulate(stones, initial=0))
        ans = dfs(0, len(stones) - 1)
        dfs.cache_clear()
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n^2) due to filling an n x n DP table and computing transitions in constant time using prefix sums. Space complexity is O(n^2) for the DP table, reducible to O(n) with optimization since only adjacent subarray results are needed at each step.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate immediately considers DP subarray state transitions.
question_mark
Candidate tries a naive greedy approach and needs redirection to subarray sums.
question_mark
Candidate correctly identifies that prefix sums optimize repeated sum computations.

warning

常见陷阱

外企场景

error
Forgetting to subtract the removed stone from the remaining sum when computing points.
error
Incorrectly defining dp state leading to miscounted score differences.
error
Overlooking base cases for single-stone subarrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow players to remove up to k stones from either end per turn.
arrow_right_alt
Modify scoring so removed stone values are added instead of remaining sums.
arrow_right_alt
Extend to three players with cyclic turns and maximize score difference for first player.

help

常见问题

外企场景

继续练习

#1728 猫和老鼠 II #1563 石子游戏 V #1872 石子游戏 VIII