企业官网建设流程全解析

LeetCode-Go 题解：1690. Stone Game VII（石子游戏 VII）区间 DP 与一维空间优化

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南以 leetcode/1690.Stone-Game-VII/README.md 为核心骨架，深入讲解 LeetCode 1690「石子游戏 VII」的博弈论建模、二维区间 DP 递推，以及 LeetCode-Go 仓库中给出的一维空间压缩 DP 优化。读完本文，你将掌握"双人取石子"类博弈问题的统一建模方法（把"最大化己方分差"收敛为同一目标），学会用前缀和计算区间和，并能理解"先写二维 DP、再按递推规律压缩到一维"的优化套路。

题目回顾：游戏规则与胜负判定

Alice 和 Bob 轮流进行游戏，Alice 先手。有n块石子排成一排，stones[i]表示从左起第i块石子的分值。每一回合，玩家可以移除最左边或最右边的石子，并获得与移除后行中剩余石子分值之和相等的得分。当行中没有石子可移除时，得分较高者获胜。

一个关键设定是：Bob 发现自己总是会输，因此他的目标不再是赢，而是尽量缩小两人的分差；Alice 的目标则是尽量扩大两人的分差。给定整数数组stones，若双方都发挥出最佳水平，返回 Alice 与 Bob 的最终分差。

约束条件（与原题一致）：

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

由于n最大为 1000，O(n²)的区间 DP 在时间和空间上都是可行的。

示例推演：理解"得分"与"分差"

示例 1：

输入：stones = [5,3,1,4,2] 输出：6

原文档给出的完整走法推演如下：

• Alice 移除 2，获得 5 + 3 + 1 + 4 = 13 分，此时 Alice = 13，Bob = 0，石子变为[5,3,1,4]；
• Bob 移除 5，获得 3 + 1 + 4 = 8 分，此时 Alice = 13，Bob = 8，石子变为[3,1,4]；
• Alice 移除 3，获得 1 + 4 = 5 分，此时 Alice = 18，Bob = 8，石子变为[1,4]；
• Bob 移除 1，获得 4 分，此时 Alice = 18，Bob = 12，石子变为[4]；
• Alice 移除 4，获得 0 分（无剩余石子），石子清空。

最终分差为 18 - 12 =6。

注意最后一步移除唯一石子时得分为 0，这是"得分等于剩余石子之和"的直接推论。

示例 2：

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

该用例与示例 1 一起出现在仓库的测试文件中（见下文"源码与测试验证"）。

解题思路：统一目标——最大化相对分差

这是本题最核心的建模步骤，原文档给出了一段非常关键的分析：

Bob 已经明确肯定是输，所以他的分数一定比 Alice 小，那么Bob - Alice分数相减一定是负数。相对分数越小，意味着差值越大。负数越大，差值越小。-50 和 -10，-10 数值大，相差小。所以 Bob 的操作是让相对分数越大。Alice 的目的也是这样，要让Alice - Bob的相对分数越大，这里是正数的越大。综上，两者的目的相同，都是让相对分数最大化。

换句话说：不必分别站在 Alice 和 Bob 两个立场上建模。无论轮到谁，当前玩家都希望"自己视角下的相对分差（当前玩家得分 − 对手得分）尽可能大"。Bob 视角下的Bob - Alice与 Alice 视角下的Alice - Bob互为相反数，但"最大化自己视角的分差"这一目标对双方完全一致，因此可以抽象出统一的区间 DP 状态。

解法二：常规区间 DP（二维 + 前缀和）

状态定义

定义dp[i][j]表示在当前区间stones[i ~ j]内，当前回合玩家能获得的最大相对分差（当前玩家得分减去对手得分）。

状态转移方程

dp[i][j] = max( sum(i + 1, j) - dp[i + 1][j], // 取走 stone[i]：本轮获得 sum(i+1, j) 分，再减去对手在剩余区间 [i+1, j] 上能获得的最大相对分差 sum(i, j - 1) - dp[i][j - 1] // 取走 stone[j]：本轮获得 sum(i, j - 1) 分，再减去对手在剩余区间 [i, j-1] 上能获得的最大相对分差 )

其中sum(i + 1, j) = stones[i+1] + stones[i+2] + …… + stones[j]，即取走左端石子后剩余区间的分值总和；sum(i, j - 1)同理。由于每次只移除一端，剩余区间长度严格递减，因此可以按区间长度从小到大递推，这正是区间 DP 的标准做法。

区间和通过前缀和数组在O(1)时间内求出：设prefixSum[k] = stones[0] + … + stones[k]，则sum(L, R) = prefixSum[R] - prefixSum[L-1]（L = 0时为prefixSum[R]）。

源码实现

仓库中的常规 DP 实现位于 leetcode/1690.Stone-Game-VII/1690. Stone Game VII.go，函数名为stoneGameVII1：

// 解法二 常规 DP func stoneGameVII1(stones []int) int { prefixSum := make([]int, len(stones)) for i := 0; i < len(stones); i++ { if i == 0 { prefixSum[i] = stones[i] } else { prefixSum[i] = prefixSum[i-1] + stones[i] } } dp := make([][]int, len(stones)) for i := range dp { dp[i] = make([]int, len(stones)) dp[i][i] = 0 } n := len(stones) for l := 2; l <= n; l++ { for i := 0; i+l <= n; i++ { dp[i][i+l-1] = max(prefixSum[i+l-1]-prefixSum[i+1]+stones[i+1]-dp[i+1][i+l-1], prefixSum[i+l-2]-prefixSum[i]+stones[i]-dp[i][i+l-2]) } } return dp[0][n-1] }

对照转移方程看这段代码：

• prefixSum[i+l-1]-prefixSum[i+1]+stones[i+1]恰好等于stones[i+1] + … + stones[i+l-1]，即sum(i+1, j)；
• prefixSum[i+l-2]-prefixSum[i]+stones[i]恰好等于stones[i] + … + stones[i+l-2]，即sum(i, j-1)；
• 基例dp[i][i] = 0：区间只剩一块石子时，移除它得 0 分，相对分差为 0；
• 外层l枚举区间长度（从 2 开始，长度 1 已由基例覆盖），内层i枚举区间左端点；
• 最终答案就是整个区间的dp[0][n-1]。

代码末尾还定义了max辅助函数（仓库源码自行实现，而非依赖 Go 1.21+ 的内置max，因此兼容更早的 Go 版本）：

func max(a, b int) int { if a > b { return a } return b }

复杂度

• 时间复杂度：O(n²)，两层循环枚举所有区间；
• 空间复杂度：O(n²)，二维dp表加一维前缀和数组。

解法一：空间压缩的一维 DP

原文档对这一解法有一段重要提示：

解法一是压缩了 DP 数组，在 DP 状态转移的时候，生成下一个dp[j]实际上是有规律的。利用这个规律可以少存一维数据，压缩空间。解法一的代码直接写出来，比较难想。先写出解法二的代码，然后找到递推规律，优化空间压缩一维，再写出解法一的代码。

也就是说，一维解法并不是"拍脑袋"写出来的，而是从二维递推式中观察到依赖关系后压缩而来。

压缩的关键观察

二维递推dp[i][j]只依赖长度短一档的两个相邻子区间：dp[i+1][j]（对应二维表的下侧）和dp[i][j-1]（对应二维表的左侧）。因此每一轮迭代只需要保存"一档长度"的数据，完全可以在一个一维数组上原地滚动覆盖。

仓库中的stoneGameVII实现如下：

// 解法一 优化空间版 DP func stoneGameVII(stones []int) int { n := len(stones) sum := make([]int, n) dp := make([]int, n) for i, d := range stones { sum[i] = d } for i := 1; i < n; i++ { for j := 0; j+i < n; j++ { if (n-i)%2 == 1 { d0 := dp[j] + sum[j] d1 := dp[j+1] + sum[j+1] if d0 > d1 { dp[j] = d0 } else { dp[j] = d1 } } else { d0 := dp[j] - sum[j] d1 := dp[j+1] - sum[j+1] if d0 < d1 { dp[j] = d0 } else { dp[j] = d1 } } sum[j] = sum[j] + stones[i+j] } } return dp[0] }

逐行拆解一维版本

• 初始化时，sum[j] = stones[j]，dp[j] = 0；
• 外层循环i从 1 到n-1，对应区间长度为i+1；
• sum[j]兼作滚动区间和：进入第i轮时，sum[j]保存的是区间[j, j+i-1]（长度i）的石子总和；每轮末尾执行sum[j] = sum[j] + stones[i+j]，把它滚动扩展为区间[j, j+i]（长度i+1）的总和，从而省掉了前缀和数组；
• dp[j]原地覆盖：进入第i轮时，dp[j]保存的是区间[j, j+i-1]的分差；本轮更新后，dp[j]变为区间[j, j+i]的分差；
• (n-i)%2奇偶分支处理轮次交替：在长度为i+1的区间上，已走过的步数为n-(i+1) = n-i-1。步数为偶数时轮到 Alice，步数为奇数时轮到 Bob。因此：
  • (n-i)%2 == 1：轮到 Alice，她希望最大化Alice - Bob，分支内比较dp[j]+sum[j]与dp[j+1]+sum[j+1]并取max；
  • 否则：轮到 Bob，Bob 最大化Bob - Alice等价于最小化Alice - Bob，分支内比较dp[j]-sum[j]与dp[j+1]-sum[j+1]并取min（符号翻转正好把"对手视角"折算回 Alice 视角）。

直观理解：dp[j] + sum[j]表示"本轮取走右端石子获得sum[j]（剩余区间[j, j+i-1]的和），再接上剩余区间[j, j+i-1]上的分差延续dp[j]"；dp[j+1] + sum[j+1]表示"取走左端石子获得sum[j+1]（剩余区间[j+1, j+i]的和），再接上dp[j+1]"。Bob 回合则是同一逻辑的镜像（减法 + 取 min）。

复杂度

• 时间复杂度：O(n²)，与二维版本相同（只压缩了空间，没有减少计算量）；
• 空间复杂度：O(n)，仅两个一维数组dp与sum，相比二维版本的O(n²)有质的提升，在n = 1000时尤为明显。

源码与测试验证

本仓库对本题的测试文件位于 leetcode/1690.Stone-Game-VII/1690. Stone Game VII_test.go，采用表驱动（table-driven）方式组织用例，两个用例恰好对应原文档的两个示例：

qs := []question1690{ { para1690{[]int{5, 3, 1, 4, 2}}, ans1690{6}, }, { para1690{[]int{7, 90, 5, 1, 100, 10, 10, 2}}, ans1690{122}, }, }

测试函数Test_Problem1690对每组用例同时调用stoneGameVII（一维版）与stoneGameVII1（二维版）并打印输入输出，两套实现互相印证，保证空间优化版与常规版结果一致：

fmt.Printf("【input】:%v 【output】:%v\n", p, stoneGameVII(p.stones)) stoneGameVII1(p.stones)

仓库根目录的 gotest.sh 展示了整个仓库的测试与覆盖率收集方式：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

也就是对leetcode/...下所有包一次性执行测试并生成统一合法的覆盖率文件coverage.txt（仓库声称 100% 测试覆盖正是通过这一流程保证的）。你可以用同样的命令单独验证本题：

go test -v ./leetcode/1690.Stone-Game-VII/

总结

通过 LeetCode-Go 仓库对 1690 题的完整讲解，可以沉淀出三个可迁移的解题能力：

1. 博弈问题的目标统一：当一方必输、只求缩小分差时，把"Alice 最大化分差"与"Bob 最小化分差"统一为"双方各自最大化自己视角的相对分差"，从而可以用同一个dp状态刻画双方行为；
2. 区间 DP + 前缀和的组合：dp[i][j] = max(sum(i+1,j) - dp[i+1][j], sum(i,j-1) - dp[i][j-1])是"双端取石子"类题目的通用骨架，区间和用前缀和数组O(1)获取，按区间长度递增递推；
3. 空间压缩的工程技巧：当递推只依赖"上一档长度"的相邻状态时，可以把二维表压缩为一维原地滚动，同时用sum[j]兼作滚动区间和，配合奇偶分支处理回合交替，将空间复杂度从O(n²)降到O(n)——而这一步的推导顺序，正如原文档强调的，是先写出常规二维解，再观察规律压缩，而不是直接硬背一维代码。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go