LeetCode 1690. 石子游戏 VII

2022-01-17 HGNULB 约 11 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 1690. 石子游戏 VII

题意分析

一排石子，两人轮流从最左端或最右端拿走一颗，拿走后得分等于剩下石子的总重量。爱丽丝先手且想让「自己的分减去对手的分」尽可能大，鲍勃想让这个差尽可能小。双方都最优时，返回这个差值。

有三点必须先看清。第一，得分来自剩下的石子而不是拿走的那颗，这与大多数石子游戏相反，直觉容易反过来。第二，只能从两端拿，所以任意时刻剩下的石子都是原数组的一段连续区间——这是整道题的结构骨架。第三，游戏一直进行到石子取完，两人各自的得分序列由整个过程决定。

两人的目标看似相反，其实可以统一：鲍勃想最小化「爱丽丝减鲍勃」，等价于他想最大化「鲍勃减爱丽丝」。也就是说，轮到谁，谁就在最大化「自己减对手」。这个对称化是把双人博弈压成单一状态函数的前提，否则得为两个玩家各写一套 DP。

剩余石子的总重量会被反复用到，而它就是某个区间的和。区间和查询在这类题里必然出现，前缀和是标配。

数据规模是石子数不超过 1000，重量不超过 1000。$n^2 = 10^6$ 完全可以接受，$n^3$ 则偏紧——这个规模明确指向「区间状态、常数转移」的设计。

边界包括：只剩一颗石子时无论谁拿，得分都是 0；只剩两颗时先手必然拿走较小的那颗以留下较大的；以及所有石子重量相同的对称情形。

解法：区间 DP

核心思路

暴力做法是搜索整棵博弈树：每一步有两个选择，深度是 n，共 $O(2^n)$ 条路径。但很快会发现大量重复——不同的拿取顺序可能留下同一个区间，而后续的最优结果只取决于这个区间，与它是怎么形成的无关。这就是无后效性，也是从搜索转向 DP 的依据。

状态定义为：dp[l][r] 表示当剩余石子恰好是区间 [l, r]、且轮到某一方行动时，该方能获得的「自己得分减去对手得分」的最大值。注意这个定义里不需要记录「现在是谁在拿」，因为双方的目标已经被对称化成同一个——都在最大化自己相对对手的领先。

转移只有两个分支。拿走左端的 stones[l] 后，本方立刻得到 $\text{sum}(l+1, r)$ 分，随后局面变成区间 [l+1, r] 且轮到对手；对手在那个局面上能取得的相对领先是 dp[l+1][r]，从本方视角看要取负再加进来。所以这一分支的值是 $\text{sum}(l+1, r) - dp[l+1][r]$。拿走右端同理，值是 $\text{sum}(l, r-1) - dp[l][r-1]$。本方取两者的较大值。

「减去子问题结果」是博弈 DP 的标志性写法，它把「对手也在最优行动」这件事编码进了转移里：对手赚得越多，本方的净领先就越少。

递归基是长度为 1 的区间：dp[i][i] = 0。此时拿走唯一那颗石子，剩下为空，得分 0，游戏结束，双方差值自然是 0。数组默认初值就是 0，不需要显式赋值。

计算顺序由依赖关系决定：dp[l][r] 依赖 dp[l+1][r] 与 dp[l][r-1]，两者的区间长度都比它小 1。所以必须按区间长度从小到大枚举，长度相同的区间之间没有依赖，内部顺序任意。

区间和用前缀和 $O(1)$ 取得。定义 prefix[i] 为前 i 个元素之和（带一位哨兵），则 $\text{sum}(a, b) = prefix[b+1] - prefix[a]$。

解题步骤

先建带哨兵位的前缀和数组，长度 n + 1，prefix[0] = 0。哨兵位让「从下标 0 开始的区间和」不用特判，是区间 DP 里省事又不易错的写法。

开 n × n 的 DP 表，长度为 1 的区间保持 0。这一层是递归基，语言的零值初始化恰好符合语义，不必额外循环赋值。

外层按区间长度从 2 递增到 n，可直接保证两个短一位的依赖已完成。也可以让左端点从大到小、右端点从小到大枚举；错误的是左端点从 0 递增，因为此时 dp[l+1][r] 尚未计算。

内层枚举左端点 l，令 r = l + len - 1，循环条件是 r < n。用长度反推右端点，比同时枚举 l 和 r 再判合法更清晰。

算出两个区间和：拿左之后剩 [l+1, r]，和为 prefix[r+1] - prefix[l+1]；拿右之后剩 [l, r-1]，和为 prefix[r] - prefix[l]。这两个下标是本题最容易写错的地方，可以用「剩下的区间左右端点分别是谁」来现场核对。

两个分支各自减去对应的子问题值，取较大者写入 dp[l][r]。减号不能漏，漏掉就变成了「双方合作最大化总分」，答案会大得离谱。

返回 dp[0][n-1]，即全区间、爱丽丝先手时的最优差值。

以 stones = [5, 3, 1, 4, 2] 走一遍，预期答案 6。前缀和 prefix = [0, 5, 8, 9, 13, 15]。

长度 2：[0,1] 拿左剩 [1,1] 和为 3、拿右剩 [0,0] 和为 5，取 $\max(3 - 0, 5 - 0) = 5$；[1,2] 同理得 $\max(1, 3) = 3$；[2,3] 得 $\max(4, 1) = 4$；[3,4] 得 $\max(2, 4) = 4$。

长度 3：[0,2] 拿左剩 [1,2] 和为 4，值 $4 - dp[1][2] = 4 - 3 = 1$；拿右剩 [0,1] 和为 8，值 $8 - dp[0][1] = 8 - 5 = 3$；取 3。[1,3] 拿左剩 [2,3] 和为 5，值 $5 - 4 = 1$；拿右剩 [1,2] 和为 4，值 $4 - 3 = 1$；取 1。[2,4] 拿左剩 [3,4] 和为 6，值 $6 - 4 = 2$；拿右剩 [2,3] 和为 5，值 $5 - 4 = 1$；取 2。

长度 4：[0,3] 拿左剩 [1,3] 和为 8，值 $8 - 1 = 7$；拿右剩 [0,2] 和为 9，值 $9 - 3 = 6$；取 7。[1,4] 拿左剩 [2,4] 和为 7，值 $7 - 2 = 5$；拿右剩 [1,3] 和为 8，值 $8 - 1 = 7$；取 7。

长度 5：[0,4] 拿左剩 [1,4] 和为 10，值 $10 - dp[1][4] = 10 - 7 = 3$；拿右剩 [0,3] 和为 13，值 $13 - dp[0][3] = 13 - 7 = 6$；取 6。

返回 dp[0][4] = 6。沿着每一步取到最大值的分支回放一遍：爱丽丝拿右端的 2，得 13 分，留下 [5,3,1,4]；鲍勃在这个局面上的最优是拿左端的 5，得 8 分，留下 [3,1,4]；爱丽丝拿左端的 3，得 5 分，留下 [1,4]；鲍勃拿左端的 1，得 4 分，留下 [4]；爱丽丝拿走最后一颗，得 0 分。爱丽丝合计 $13 + 5 + 0 = 18$，鲍勃合计 $8 + 4 = 12$，差值正是 6，与 DP 结果吻合。

代码实现

class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        // 带哨兵位的前缀和，sum(a, b) = prefix[b + 1] - prefix[a]。
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }

        // dp[l][l] = 0 由零值初始化天然满足。
        int[][] dp = new int[n][n];
        for (int len = 2; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                int sumLeft = prefix[r + 1] - prefix[l + 1];
                int sumRight = prefix[r] - prefix[l];
                // 减去子问题结果，编码「对手也在最优行动」。
                int takeLeft = sumLeft - dp[l + 1][r];
                int takeRight = sumRight - dp[l][r - 1];
                dp[l][r] = Math.max(takeLeft, takeRight);
            }
        }
        return dp[0][n - 1];
    }
}

func stoneGameVII(stones []int) int {
	n := len(stones)
	// 带哨兵位的前缀和，sum(a, b) = prefix[b+1] - prefix[a]。
	prefix := make([]int, n+1)
	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + stones[i]
	}

	// dp[l][l] = 0 由零值初始化天然满足。
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}

	for length := 2; length <= n; length++ {
		for l := 0; l+length-1 < n; l++ {
			r := l + length - 1
			sumLeft := prefix[r+1] - prefix[l+1]
			sumRight := prefix[r] - prefix[l]
			// 减去子问题结果，编码「对手也在最优行动」。
			takeLeft := sumLeft - dp[l+1][r]
			takeRight := sumRight - dp[l][r-1]
			if takeLeft > takeRight {
				dp[l][r] = takeLeft
			} else {
				dp[l][r] = takeRight
			}
		}
	}

	return dp[0][n-1]
}

复杂度分析

时间复杂度：$O(n^2)$。状态数是所有区间 $\frac{n(n+1)}{2}$ 个，每个状态只需比较两个分支，转移是 $O(1)$——这得益于前缀和把区间求和压成了常数。$n \le 1000$ 时约 50 万次计算，非常宽裕。

空间复杂度：$O(n^2)$，二维 DP 表。因为 dp[l][r] 只依赖长度小 1 的两个状态，理论上可以按长度滚动成一维，把空间降到 $O(n)$，但下标映射会变得晦涩；本题规模下二维表只占约 4 MB，不必优化。

关键点总结

「只能从两端操作」几乎必然导出区间 DP：剩余部分永远是一段连续区间，状态天然由左右端点刻画。识别出这个结构，题目就只剩转移方程要推。

博弈题要先把双方目标对称化成「轮到谁，谁就最大化自己减对手」，这样一个状态函数就够了。做不到对称化时（比如两人规则不同）才需要多开一维记录当前玩家。

转移里的减号是博弈 DP 的灵魂：本轮收益 - 对手在子局面的最优领先。能解释这个减号，就说明真正理解了「对手也在最优行动」如何被编码进递推。

区间 DP 的枚举顺序由依赖决定，必须按区间长度递增。写成按左端点或右端点遍历时，一定要先确认所依赖的子区间已经算好。

前缀和加哨兵位能让所有区间和查询统一成一个减法，省掉端点特判。区间 DP 里凡是转移涉及区间统计量，都应该先把这类查询降到 $O(1)$。

面试视角：先描述博弈树搜索并指出 $O(2^n)$ 与重复子问题，再给出「剩余总是连续区间」的观察引出状态定义，然后推导带减号的转移，最后说明枚举顺序。面试官常追问「为什么状态里不用记谁在拿」，要能用对称化回答；再追问「和 877 石子游戏有什么不同」，答案是那题得分来自拿走的石子且有先手必胜的数学结论，本题得分来自剩余部分、没有简洁结论，只能老实做 DP。

易错点总结

错误写法：转移写成 sumLeft + dp[l+1][r]。用例 stones = [5, 3, 1, 4, 2] 会变成双方合作累计收益，算出 35，正确答案是 6。

错误写法：得分记成拿走那颗石子的重量。用例 stones = [5, 3, 1, 4, 2] → 题意被完全改写，算出的是「拿走石子之和的差」，答案与 6 无关。

错误写法：sumLeft 写成 prefix[r+1] - prefix[l]。用例 stones = [5, 3, 1, 4, 2] → [0,1] 区间拿左后的剩余和算成 8 而不是 3，dp[0][1] 变成 8，误差沿长度逐层放大，最终答案偏大。

错误写法：sumRight 写成 prefix[r+1] - prefix[l]。用例 stones = [5, 3, 1, 4, 2] → 把「拿走右端后剩余」算成了整个区间的和，dp[0][1] 变成 8，答案错误。

错误写法：外层按左端点从 0 到 n-1 遍历，内层按右端点递增。用例 stones = [5, 3, 1, 4, 2] → 计算 dp[0][4] 时 dp[1][4] 还是初值 0，takeLeft 算成 10，答案变成 10，正确答案是 6。

错误写法：区间长度从 1 开始枚举。用例 stones = [5] → len = 1 时 r = l，会访问 dp[l][l-1]，l = 0 时下标为 -1，Java 抛越界异常、Go 触发 panic。

错误写法：把 dp[i][i] 初始化成 stones[i]。用例 stones = [5, 3] → dp[0][1] 算成 $\max(3 - 3, 5 - 5) = 0$，正确答案是 5；单颗石子被拿走后剩余为空，差值必须是 0。

错误写法：额外用一维记录当前玩家并对鲍勃取最小值，但两处的区间和用了同一个方向。用例 stones = [5, 3, 1, 4, 2] → 若最小化分支忘记同步翻转符号，两套逻辑会互相抵消，答案在正负之间摇摆，与 6 无关。

错误写法：前缀和不带哨兵位，写成 prefix[i] = stones[0] + ... + stones[i]，却仍用 prefix[r+1] - prefix[l+1]。用例 stones = [5, 3, 1, 4, 2] → r = n-1 时访问 prefix[n] 越界；即便加了长度也会因为定义错位而算错每一个区间和。

错误写法：把 dp[l][r] 定义成「当前玩家在该区间能拿到的总分」而不是差值。用例 stones = [5, 3, 1] → 按总分定义会写出 dp[0][2] = max(4 + dp[1][2], 8 + dp[0][1]) 这类把对手得分也加进来的转移，算出 11，正确答案是 3。

相似题目

题目	难度	考察点
486. 预测赢家	中等	同样是两端取数的差值博弈，但得分是拿走的那个数，转移里没有区间和
877. 石子游戏	中等	与 486 结构相同，但堆数为偶且总和为奇，存在先手必胜的数学结论可绕过 DP
1563. 石子游戏 V	困难	操作从取两端变成任意切分，转移要枚举分割点，复杂度升到 $O(n^3)$
292. Nim 游戏	简单	纯博弈结论题，靠必败态周期性直接判断，展示并非所有博弈题都需要 DP
312. 戳气球	困难	区间 DP 的经典难题，需要反向思考「最后戳破哪个」才能让子区间独立
1000. 合并石头的最低成本	困难	区间 DP 加一维「合并成几堆」，展示状态维度如何随合并规则增长
516. 最长回文子序列	中等	同样按区间长度递推、依赖两端收缩，但没有对抗性，转移里不需要减号
面试题 08.14. 布尔运算	中等	区间 DP 加「结果为真 / 为假」两个维度，转移要按运算符分类讨论