LeetCode 877 Stone Game 取石子游戏全解：从区间 DP 递进到 O(1) 数学结论

LeetCode 877 Stone Game 取石子游戏全解：从区间 DP 递进到 O(1) 数学结论

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇技术指南以本仓库 articles/stone-game.md 为核心骨架，完整讲解 LeetCode 877（Stone Game）这道经典的双人博弈 + 区间 DP题。文章按"朴素递归 → 自顶向下记忆化 → 自底向上 DP → 空间优化 DP → 直接返回 True"五层递进展开，每一层都给出可直接运行的代码与复杂度分析，并辅以仓库中真实的 C++、Kotlin 实现作为源码级佐证。读完本文，你将掌握区间 DP 的通用建模方法、回合归属判定技巧，以及一眼识破"先手必胜"类数学结论的分析能力。

1. 题目背景与前置知识

1.1 题目描述

Alice 和 Bob 玩一个取石子游戏：有一排偶数堆石子，每堆石子数量piles[i]为正整数，且所有石子总数是奇数（保证不会出现平局）。两人轮流取石子，Alice 先手，每回合只能从这一排的最左端或最右端拿走一整堆，直到取完。最终石子多的人获胜。假设两人都以最优策略游戏，返回true表示 Alice 必胜，否则返回false。

仓库 cpp/0877-stone-game.cpp 的文件头注释完整记录了这道题的原题信息与一个运行示例：

Ex: Input: piles = [5,3,4,5] Output: true Explanation: Alice starts first, and can only take the first 5 or the last 5. Say she takes the first 5, so that the row becomes [3, 4, 5]. If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points. If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.

核心约束归纳为三条：

• piles.length为偶数；
• 每堆石子数为正整数，总和为奇数（无平局）；
• 每回合只能取当前区间[l, r]的左端或右端。

1.2 前置知识要求

原文档在开始解题前明确了四类必备基础，这也是掌握本文的前提：

1.3 本仓库中的实现分布

在 README.md 的完成度表格中，0877 - Stone Game一行标注了本仓库已收录的实现：cpp/0877-stone-game.cpp 与 kotlin/0877-stone-game.kt；同系列题目1140 - Stone Game II（java/1140-stone-game-ii.java、kotlin/1140-stone-game-ii.kt）与1406 - Stone Game III（kotlin/1406-stone-game-iii.kt、c/1406-stone-game-iii.c）也有对应解法，可作为延伸阅读。

2. 方法一：朴素递归（区间搜索）

2.1 直觉（Intuition）

这是一个双人博弈：Alice 和 Bob 轮流从piles的两端取石子，双方都最优地最大化自己的得分。我们可以用递归模拟整个过程——递归函数跟踪当前剩余区间[l, r]，并根据区间长度判断当前轮到谁：区间长度为偶数时轮到 Alice（因为初始堆数为偶数且 Alice 先手）。Alice 的每一步都试图最大化自己的得分，而 Bob 的落子会改变 Alice 之后能取到的石子。

2.2 算法步骤

1. 定义递归函数dfs(l, r)：返回子数组[l, r]上 Alice 能取得的最大分数；
2. 若l > r，说明没有剩余石子，返回0；
3. 判断当前是否 Alice 的回合：剩余堆数(r - l + 1)为偶数时是 Alice 回合（代码中等价写作(r - l) % 2 == 0）；
4. 若是 Alice 回合，她可以取左端或右端，将取值累加进分数，递归并取"取左 / 取右"两种选择的最大值；
5. 若是 Bob 回合，他同样最优取子，但我们只追踪 Alice 的分数（Bob 的取子对 Alice 分数贡献为0）；
6. 最后比较 Alice 得分与total - alice_score（Bob 得分），判断 Alice 是否获胜。

2.3 代码实现

class Solution: def stoneGame(self, piles: List[int]) -> bool: def dfs(l, r): if l > r: return 0 even = (r - l) % 2 == 0 left = piles[l] if even else 0 right = piles[r] if even else 0 return max(dfs(l + 1, r) + left, dfs(l, r - 1) + right) total = sum(piles) alice_score = dfs(0, len(piles) - 1) return alice_score > total - alice_score

原文档同一小节还给出了 Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 的等价实现，逻辑完全一致：核心都是"回合判定 + 两端取最大"。例如 Java 版本使用Math.max(dfs(l + 1, r, piles) + left, dfs(l, r - 1, piles) + right)，C++ 版本使用max(...)与vector<int>& piles引用传参，Go 版本则以内嵌闭包var dfs func(l, r int) int实现。

2.4 复杂度分析

• 时间复杂度：$O(2 ^ n)$ —— 每个状态最多分支为取左/取右两种选择，形成指数级搜索树；
• 空间复杂度：$O(n)$ —— 递归调用栈的最大深度为区间长度。

由于存在大量重叠子问题（同一个[l, r]可以通过不同的取子顺序到达），指数级递归显然不是高效解，因此引出方法二的记忆化优化。

3. 方法二：动态规划（自顶向下 / 记忆化递归）

3.1 直觉

朴素递归存在重叠子问题：同一个(l, r)区间会通过不同的移动序列被反复计算。把每个(l, r)的结果缓存下来，就能避免重复计算，将复杂度从指数级降到多项式级。

3.2 算法步骤

1. 建立二维记忆表dp，初始化为-1（或使用哈希表(l, r) -> score）；
2. 递归函数入口先查表：若dp[l][r]已计算，直接返回缓存值；
3. 其余计算逻辑与朴素递归完全一致（回合判定 + 两端取最大）；
4. 返回值前先把结果写入dp[l][r]；
5. 最终答案：dp[0][n-1]（Alice 最优得分）是否大于total - dp[0][n-1]（Bob 得分）。

3.3 代码实现

class Solution: def stoneGame(self, piles: List[int]) -> bool: dp = {} def dfs(l, r): if l > r: return 0 if (l, r) in dp: return dp[(l, r)] even = (r - l) % 2 == 0 left = piles[l] if even else 0 right = piles[r] if even else 0 dp[(l, r)] = max(dfs(l + 1, r) + left, dfs(l, r - 1) + right) return dp[(l, r)] total = sum(piles) alice_score = dfs(0, len(piles) - 1) return alice_score > total - alice_score

仓库源码佐证：本仓库 kotlin/0877-stone-game.kt 正是这一思路的 Kotlin 实现——它用Array(piles.size) { IntArray(piles.size) { -1 } }建立二维缓存，递归函数dfs(left, right)中先判断dp[left][right] != -1命中缓存，再以maxOf(dfs(left + 1, right) + if (isEven) piles[left] else 0, dfs(left, right - 1) + if (isEven) piles[right] else 0)完成状态转移，最后用dfs(0, piles.lastIndex) > (piles.sum() ?: 0) / 2判定胜负。这份真实代码与原文档的伪代码结构一一对应，可作为对照阅读。

3.4 复杂度分析

• 时间复杂度：$O(n ^ 2)$ —— 状态总数是 $n \times n$ 个(l, r)组合，每个状态 O(1) 转移；
• 空间复杂度：$O(n ^ 2)$ —— 二维记忆表。

4. 方法三：动态规划（自底向上）

4.1 直觉

不用递归 + 记忆化，而是按区间长度递增的顺序迭代填充 DP 表。对每个区间[l, r]，它的值只依赖已经求解过的更小区间[l+1, r]与[l, r-1]，因此只要保证遍历顺序先小后大即可。

4.2 算法步骤

1. 建立n x n的二维 DP 表；
2. 外层循环l从n-1递减到0（保证更小区间先被求解）；
3. 内层循环r从l递增到n-1；
4. 依据(r - l) % 2判断当前回合归属；
5. 边界情况l == r：若轮到 Alice 则取走该堆，否则为0；
6. 更大区间：取"取左端"与"取右端"的最大值（仅在 Alice 回合累加堆值）；
7. 返回dp[0][n-1] > total - dp[0][n-1]。

4.3 代码实现

class Solution: def stoneGame(self, piles: List[int]) -> bool: n = len(piles) dp = [[0] * n for _ in range(n)] for l in range(n - 1, -1, -1): for r in range(l, n): even = (r - l) % 2 == 0 left = piles[l] if even else 0 right = piles[r] if even else 0 if l == r: dp[l][r] = left else: dp[l][r] = max(dp[l + 1][r] + left, dp[l][r - 1] + right) total = sum(piles) alice_score = dp[0][n - 1] return alice_score > total - alice_score

要点是遍历顺序：l从大到小、r从小到大，这样计算dp[l][r]时，dp[l+1][r]（下一行、同列）与dp[l][r-1]（同行、左列）都已经是最终值。

4.4 复杂度分析

• 时间复杂度：$O(n ^ 2)$；
• 空间复杂度：$O(n ^ 2)$。

5. 方法四：动态规划（空间优化）

5.1 直觉

观察状态转移式，dp[l][r]只依赖dp[l+1][r]与dp[l][r-1]。当外层按l从右到左、内层按r从左到右遍历时，dp[l+1][r]恰好是上一轮迭代留下的旧值（即当前一维数组中的dp[r]），而dp[l][r-1]是本轮刚更新的dp[r-1]。因此可以把二维表压缩成一维数组。

5.2 算法步骤

1. 建立长度为n的一维 DP 数组；
2. 外层循环l从n-1递减到0；
3. 内层循环r从l递增到n-1；
4. 更新前的dp[r]代表旧值dp[l+1][r]，dp[r-1]代表dp[l][r-1]；
5. 用取左/取右的最大值原地更新dp[r]；
6. 返回dp[n-1] > total - dp[n-1]。

5.3 代码实现

class Solution: def stoneGame(self, piles: List[int]) -> bool: n = len(piles) dp = [0] * n for l in reversed(range(n)): for r in range(l, n): even = ((r - l) % 2 == 0) left = piles[l] if even else 0 right = piles[r] if even else 0 if l == r: dp[r] = left else: dp[r] = max(dp[r] + left, dp[r - 1] + right) total = sum(piles) alice_score = dp[n - 1] return alice_score > (total - alice_score)

注意这里的原地更新必须小心：dp[r]右侧引用的是旧值（代表dp[l+1][r]），而dp[r-1]是本轮新值（代表dp[l][r-1]），这正是遍历顺序保证的关键性质。

5.4 复杂度分析

• 时间复杂度：$O(n ^ 2)$；
• 空间复杂度：$O(n)$。

6. 方法五：直接返回 TRUE（数学必胜结论）

6.1 直觉

这是本题最精彩的洞察：石子堆数为偶数 + 总和为奇数 ⇒ Alice 必胜。

具体论证如下：

• 由于堆数为偶数，所有堆可以按下标奇偶分成两组：偶数下标堆{0, 2, 4, ...}与奇数下标堆{1, 3, 5, ...}；
• 无论从哪一端取，取完一整行石子后，任意一方拿到的必然恰好是其中一组（偶数下标组或奇数下标组）——这是"只能从两端取"这个规则带来的结构性约束；
• 因为总和是奇数，两组之和不可能相等，必有一组的和更大；
• Alice 先手，她可以主动选择要"偶数下标组"还是"奇数下标组"：只要第一步取走一端后，始终在对手取完后再取同奇偶性的堆，就能强制自己拿到和更大的那一组，从而保证获胜。

6.2 算法步骤

1. 直接返回true。

class Solution: def stoneGame(self, piles: List[int]) -> bool: return True

6.3 仓库中的配对实现

本仓库 cpp/0877-stone-game.cpp 给出了一个基于两端配对的 O(n) 实现，与上述数学结论相互印证：它把piles[i]与piles[size - 1 - i]配成一对，Alice 取每对中的max、Bob 取每对中的min，累加后比较：

class Solution { public: bool stoneGame(vector<int>& piles) { int alice = 0, bob = 0, size = piles.size(); for(int i = 0 ; i < size/2; i++) { alice = alice + max( piles[i], piles[size - 1- i] ); bob = bob + min( piles[i], piles[size - 1- i] ); } if(alice > bob) return true; return false; } };

该实现的正确性依赖两条性质：每对中 Alice 拿max必然不小于 Bob 拿的min，因此逐对累加后alice >= bob；又因总和为奇数，至少存在一对取值不相等，故alice > bob严格成立。从源码结构看，这份实现的时间复杂度为 $O(n)$（循环size/2次），额外空间为 $O(1)$，是"数学必胜结论"之外又一个简洁的工程化解法。

6.4 复杂度分析

• 时间复杂度：$O(1)$；
• 空间复杂度：$O(1)$。

7. 常见陷阱（Common Pitfalls）

原文档最后总结了三个高频易错点，这里完整保留并展开说明：

7.1 过度复杂化解法

由于"偶数堆 + 奇数总和 ⇒ Alice 必胜"这一数学性质，题目可以直接返回true。但很多解题者没有识别该性质，直接实现了完整的 DP。DP 解法本身完全正确且有教学价值，但理解"为什么 Alice 必胜"才是更深的题目分析，能帮你把这类博弈题一眼看穿。

7.2 混淆回合归属

在 DP 解法中，根据区间[l, r]判断轮到谁非常容易出错。Alice 在剩余堆数为偶数时行动（游戏以偶数堆开始且她先手），即(r - l + 1) % 2 == 0或等价的(r - l) % 2 == 1表示 Alice 回合。这里**差一错误（off-by-one）**极常见，务必反复验证。

7.3 最终比较方向写错

题目问的是 Alice是否获胜（严格大于），而不是平局或非负。如果写成alice_score >= total - alice_score就会得到错误结果。虽然本题因为总和为奇数、所有值为正整数而不可能出现平局，但比较符号仍应严格使用>。

8. 五层解法总览

从工程效率看，方法五最优；从算法学习价值看，方法二、三、四覆盖了"递归 → 记忆化 → 递推 → 空间压缩"的完整 DP 进阶路径，是掌握区间 DP的绝佳范本。仓库内的 cpp/0877-stone-game.cpp（配对法）与 kotlin/0877-stone-game.kt（记忆化递归）恰好体现了"数学捷径"与"通用 DP"两条路线，读者可在本地分别运行对照。若想继续挑战，同系列题目 articles/stone-game-ii.md（1140，可一次取 1~2M 堆，需区间 DP + 前缀和）与 articles/stone-game-iii.md（1406，三人取子变体，需从后向前递推）在本仓库均有题解与实现，适合串联学习。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode