尧图网站建设  数学结论)
LeetCode 877 Stone Game 取石子游戏全解从区间 DP 递进到 O(1) 数学结论【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以本仓库 articles/stone-game.md 为核心骨架完整讲解 LeetCode 877Stone 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 前置知识要求原文档在开始解题前明确了四类必备基础这也是掌握本文的前提前置知识点在本题的落点动态规划区间 DP对区间[l, r]计算最优结果子问题按区间收缩的方式递推博弈论 / 双人游戏建模轮流取子、双方都最优的回合制游戏递归 记忆化用缓存重叠子问题把指数级递归改造为多项式级 DP数学推理识别偶数堆 奇数总数的结构性质得到 O(1) 直接结论1.3 本仓库中的实现分布在 README.md 的完成度表格中0877 - Stone Game一行标注了本仓库已收录的实现cpp/0877-stone-game.cpp 与 kotlin/0877-stone-game.kt同系列题目1140 - Stone Game IIjava/1140-stone-game-ii.java、kotlin/1140-stone-game-ii.kt与1406 - Stone Game IIIkotlin/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 算法步骤定义递归函数dfs(l, r)返回子数组[l, r]上 Alice 能取得的最大分数若l r说明没有剩余石子返回0判断当前是否 Alice 的回合剩余堆数(r - l 1)为偶数时是 Alice 回合代码中等价写作(r - l) % 2 0若是 Alice 回合她可以取左端或右端将取值累加进分数递归并取取左 / 取右两种选择的最大值若是 Bob 回合他同样最优取子但我们只追踪 Alice 的分数Bob 的取子对 Alice 分数贡献为0最后比较 Alice 得分与total - alice_scoreBob 得分判断 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(...)与vectorint 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 算法步骤建立二维记忆表dp初始化为-1或使用哈希表(l, r) - score递归函数入口先查表若dp[l][r]已计算直接返回缓存值其余计算逻辑与朴素递归完全一致回合判定 两端取最大返回值前先把结果写入dp[l][r]最终答案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]它的值只依赖已经求解过的更小区间[l1, r]与[l, r-1]因此只要保证遍历顺序先小后大即可。4.2 算法步骤建立n x n的二维 DP 表外层循环l从n-1递减到0保证更小区间先被求解内层循环r从l递增到n-1依据(r - l) % 2判断当前回合归属边界情况l r若轮到 Alice 则取走该堆否则为0更大区间取取左端与取右端的最大值仅在 Alice 回合累加堆值返回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[l1][r]下一行、同列与dp[l][r-1]同行、左列都已经是最终值。4.4 复杂度分析时间复杂度$O(n ^ 2)$空间复杂度$O(n ^ 2)$。5. 方法四动态规划空间优化5.1 直觉观察状态转移式dp[l][r]只依赖dp[l1][r]与dp[l][r-1]。当外层按l从右到左、内层按r从左到右遍历时dp[l1][r]恰好是上一轮迭代留下的旧值即当前一维数组中的dp[r]而dp[l][r-1]是本轮刚更新的dp[r-1]。因此可以把二维表压缩成一维数组。5.2 算法步骤建立长度为n的一维 DP 数组外层循环l从n-1递减到0内层循环r从l递增到n-1更新前的dp[r]代表旧值dp[l1][r]dp[r-1]代表dp[l][r-1]用取左/取右的最大值原地更新dp[r]返回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[l1][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 算法步骤直接返回true。class Solution: def stoneGame(self, piles: List[int]) - bool: return True6.3 仓库中的配对实现本仓库 cpp/0877-stone-game.cpp 给出了一个基于两端配对的 O(n) 实现与上述数学结论相互印证它把piles[i]与piles[size - 1 - i]配成一对Alice 取每对中的max、Bob 取每对中的min累加后比较class Solution { public: bool stoneGame(vectorint 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. 五层解法总览方法核心思想时间复杂度空间复杂度朴素递归区间搜索模拟双方最优$O(2 ^ n)$$O(n)$自顶向下 DP记忆化缓存(l, r)结果$O(n ^ 2)$$O(n ^ 2)$自底向上 DP按区间长度递增填表$O(n ^ 2)$$O(n ^ 2)$空间优化 DP一维滚动数组原地更新$O(n ^ 2)$$O(n)$直接返回 True奇偶分组数学必胜结论$O(1)$$O(1)$从工程效率看方法五最优从算法学习价值看方法二、三、四覆盖了递归 → 记忆化 → 递推 → 空间压缩的完整 DP 进阶路径是掌握区间 DP的绝佳范本。仓库内的 cpp/0877-stone-game.cpp配对法与 kotlin/0877-stone-game.kt记忆化递归恰好体现了数学捷径与通用 DP两条路线读者可在本地分别运行对照。若想继续挑战同系列题目 articles/stone-game-ii.md1140可一次取 1~2M 堆需区间 DP 前缀和与 articles/stone-game-iii.md1406三人取子变体需从后向前递推在本仓库均有题解与实现适合串联学习。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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 877Stone 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 前置知识要求原文档在开始解题前明确了四类必备基础这也是掌握本文的前提前置知识点在本题的落点动态规划区间 DP对区间[l, r]计算最优结果子问题按区间收缩的方式递推博弈论 / 双人游戏建模轮流取子、双方都最优的回合制游戏递归 记忆化用缓存重叠子问题把指数级递归改造为多项式级 DP数学推理识别偶数堆 奇数总数的结构性质得到 O(1) 直接结论1.3 本仓库中的实现分布在 README.md 的完成度表格中0877 - Stone Game一行标注了本仓库已收录的实现cpp/0877-stone-game.cpp 与 kotlin/0877-stone-game.kt同系列题目1140 - Stone Game IIjava/1140-stone-game-ii.java、kotlin/1140-stone-game-ii.kt与1406 - Stone Game IIIkotlin/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 算法步骤定义递归函数dfs(l, r)返回子数组[l, r]上 Alice 能取得的最大分数若l r说明没有剩余石子返回0判断当前是否 Alice 的回合剩余堆数(r - l 1)为偶数时是 Alice 回合代码中等价写作(r - l) % 2 0若是 Alice 回合她可以取左端或右端将取值累加进分数递归并取取左 / 取右两种选择的最大值若是 Bob 回合他同样最优取子但我们只追踪 Alice 的分数Bob 的取子对 Alice 分数贡献为0最后比较 Alice 得分与total - alice_scoreBob 得分判断 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(...)与vectorint 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 算法步骤建立二维记忆表dp初始化为-1或使用哈希表(l, r) - score递归函数入口先查表若dp[l][r]已计算直接返回缓存值其余计算逻辑与朴素递归完全一致回合判定 两端取最大返回值前先把结果写入dp[l][r]最终答案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]它的值只依赖已经求解过的更小区间[l1, r]与[l, r-1]因此只要保证遍历顺序先小后大即可。4.2 算法步骤建立n x n的二维 DP 表外层循环l从n-1递减到0保证更小区间先被求解内层循环r从l递增到n-1依据(r - l) % 2判断当前回合归属边界情况l r若轮到 Alice 则取走该堆否则为0更大区间取取左端与取右端的最大值仅在 Alice 回合累加堆值返回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[l1][r]下一行、同列与dp[l][r-1]同行、左列都已经是最终值。4.4 复杂度分析时间复杂度$O(n ^ 2)$空间复杂度$O(n ^ 2)$。5. 方法四动态规划空间优化5.1 直觉观察状态转移式dp[l][r]只依赖dp[l1][r]与dp[l][r-1]。当外层按l从右到左、内层按r从左到右遍历时dp[l1][r]恰好是上一轮迭代留下的旧值即当前一维数组中的dp[r]而dp[l][r-1]是本轮刚更新的dp[r-1]。因此可以把二维表压缩成一维数组。5.2 算法步骤建立长度为n的一维 DP 数组外层循环l从n-1递减到0内层循环r从l递增到n-1更新前的dp[r]代表旧值dp[l1][r]dp[r-1]代表dp[l][r-1]用取左/取右的最大值原地更新dp[r]返回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[l1][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 算法步骤直接返回true。class Solution: def stoneGame(self, piles: List[int]) - bool: return True6.3 仓库中的配对实现本仓库 cpp/0877-stone-game.cpp 给出了一个基于两端配对的 O(n) 实现与上述数学结论相互印证它把piles[i]与piles[size - 1 - i]配成一对Alice 取每对中的max、Bob 取每对中的min累加后比较class Solution { public: bool stoneGame(vectorint 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. 五层解法总览方法核心思想时间复杂度空间复杂度朴素递归区间搜索模拟双方最优$O(2 ^ n)$$O(n)$自顶向下 DP记忆化缓存(l, r)结果$O(n ^ 2)$$O(n ^ 2)$自底向上 DP按区间长度递增填表$O(n ^ 2)$$O(n ^ 2)$空间优化 DP一维滚动数组原地更新$O(n ^ 2)$$O(n)$直接返回 True奇偶分组数学必胜结论$O(1)$$O(1)$从工程效率看方法五最优从算法学习价值看方法二、三、四覆盖了递归 → 记忆化 → 递推 → 空间压缩的完整 DP 进阶路径是掌握区间 DP的绝佳范本。仓库内的 cpp/0877-stone-game.cpp配对法与 kotlin/0877-stone-game.kt记忆化递归恰好体现了数学捷径与通用 DP两条路线读者可在本地分别运行对照。若想继续挑战同系列题目 articles/stone-game-ii.md1140可一次取 1~2M 堆需区间 DP 前缀和与 articles/stone-game-iii.md1406三人取子变体需从后向前递推在本仓库均有题解与实现适合串联学习。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考