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

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.length2 n 10001 stones[i] 1000由于n最大为 1000O(n²)的区间 DP 在时间和空间上都是可行的。示例推演理解得分与分差示例 1输入stones [5,3,1,4,2] 输出6原文档给出的完整走法推演如下Alice 移除 2获得 5 3 1 4 13 分此时 Alice 13Bob 0石子变为[5,3,1,4]Bob 移除 5获得 3 1 4 8 分此时 Alice 13Bob 8石子变为[3,1,4]Alice 移除 3获得 1 4 5 分此时 Alice 18Bob 8石子变为[1,4]Bob 移除 1获得 4 分此时 Alice 18Bob 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(i1, j) 分再减去对手在剩余区间 [i1, j] 上能获得的最大相对分差 sum(i, j - 1) - dp[i][j - 1] // 取走 stone[j]本轮获得 sum(i, j - 1) 分再减去对手在剩余区间 [i, j-1] 上能获得的最大相对分差 )其中sum(i 1, j) stones[i1] stones[i2] …… 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; il n; i { dp[i][il-1] max(prefixSum[il-1]-prefixSum[i1]stones[i1]-dp[i1][il-1], prefixSum[il-2]-prefixSum[i]stones[i]-dp[i][il-2]) } } return dp[0][n-1] }对照转移方程看这段代码prefixSum[il-1]-prefixSum[i1]stones[i1]恰好等于stones[i1] … stones[il-1]即sum(i1, j)prefixSum[il-2]-prefixSum[i]stones[i]恰好等于stones[i] … stones[il-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[i1][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; ji n; j { if (n-i)%2 1 { d0 : dp[j] sum[j] d1 : dp[j1] sum[j1] if d0 d1 { dp[j] d0 } else { dp[j] d1 } } else { d0 : dp[j] - sum[j] d1 : dp[j1] - sum[j1] if d0 d1 { dp[j] d0 } else { dp[j] d1 } } sum[j] sum[j] stones[ij] } } return dp[0] }逐行拆解一维版本初始化时sum[j] stones[j]dp[j] 0外层循环i从 1 到n-1对应区间长度为i1sum[j]兼作滚动区间和进入第i轮时sum[j]保存的是区间[j, ji-1]长度i的石子总和每轮末尾执行sum[j] sum[j] stones[ij]把它滚动扩展为区间[j, ji]长度i1的总和从而省掉了前缀和数组dp[j]原地覆盖进入第i轮时dp[j]保存的是区间[j, ji-1]的分差本轮更新后dp[j]变为区间[j, ji]的分差(n-i)%2奇偶分支处理轮次交替在长度为i1的区间上已走过的步数为n-(i1) n-i-1。步数为偶数时轮到 Alice步数为奇数时轮到 Bob。因此(n-i)%2 1轮到 Alice她希望最大化Alice - Bob分支内比较dp[j]sum[j]与dp[j1]sum[j1]并取max否则轮到 BobBob 最大化Bob - Alice等价于最小化Alice - Bob分支内比较dp[j]-sum[j]与dp[j1]-sum[j1]并取min符号翻转正好把对手视角折算回 Alice 视角。直观理解dp[j] sum[j]表示本轮取走右端石子获得sum[j]剩余区间[j, ji-1]的和再接上剩余区间[j, ji-1]上的分差延续dp[j]dp[j1] sum[j1]表示取走左端石子获得sum[j1]剩余区间[j1, ji]的和再接上dp[j1]。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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也就是对leetcode/...下所有包一次性执行测试并生成统一合法的覆盖率文件coverage.txt仓库声称 100% 测试覆盖正是通过这一流程保证的。你可以用同样的命令单独验证本题go test -v ./leetcode/1690.Stone-Game-VII/总结通过 LeetCode-Go 仓库对 1690 题的完整讲解可以沉淀出三个可迁移的解题能力博弈问题的目标统一当一方必输、只求缩小分差时把Alice 最大化分差与Bob 最小化分差统一为双方各自最大化自己视角的相对分差从而可以用同一个dp状态刻画双方行为区间 DP 前缀和的组合dp[i][j] max(sum(i1,j) - dp[i1][j], sum(i,j-1) - dp[i][j-1])是双端取石子类题目的通用骨架区间和用前缀和数组O(1)获取按区间长度递增递推空间压缩的工程技巧当递推只依赖上一档长度的相邻状态时可以把二维表压缩为一维原地滚动同时用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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考