LeetCode 877. 石子游戏

2025-02-01 HGNULB 约 6 分钟

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

分类

题目描述

✅ 877. 石子游戏

题意分析

一排石子堆摆在桌上，两人轮流从最左端或最右端整堆取走，全部取完后石子总数多的一方获胜。给定每堆的数量 piles，问先手在双方都发挥最优的前提下能否获胜，返回布尔值。

「双方都发挥最优」是这类题的核心措辞，它把问题从「枚举所有取法」变成了「每一步都由当前行动方按对自己最有利的方式决定」。这意味着不能贪心地每次拿更大的一端——拿走大的可能给对手让出更大的一端。同时它也保证了博弈结果是唯一确定的，不存在运气成分，所以答案完全由 piles 决定。

只能从两端取，这一条极强：任意时刻剩下的石子必然是原数组的一个连续区间。也就是说整个游戏的状态空间不是 $2^n$ 个子集，而只有 $O(n^2)$ 个区间，规模一下子落进可枚举的范围。这是「从两端操作」类题目最值得抓住的信号。

约束里还写明堆数是偶数、石子总数是奇数。偶数保证两人取的堆数相同，奇数保证不会平局、胜负必定分明。这两条其实暗示了一个纯数学结论，但它只在这道题的特定约束下成立，换成奇数堆或允许平局立刻失效，所以更该掌握的是能推广的通用解法。

边界要盯住：区间长度为 1 时只有一种取法；区间为空表示游戏结束，双方分差为 0；最终判定用「先手减后手的分差是否大于 0」，因为总数为奇数所以分差不可能为 0，不必纠结等号。

解法：区间 DP 计算先手分差

核心思路

每次只能拿一端，所以任意时刻剩余部分都是连续区间。暴力搜索会反复求解相同区间，把结果记为区间 DP 即可消除重复。

定义 dp[i][j]：只剩区间 [i, j] 且轮到当前玩家时，当前玩家最终能领先对手的最大分差。这里必须用「分差」而不是某一方的绝对得分，因为换手后状态主语也随之变成对手。

若取左端，当前玩家先得 piles[i]，随后对手能在 [i + 1, j] 领先 dp[i + 1][j]，所以本方最终分差是 piles[i] - dp[i + 1][j]；取右端同理。双方都最优，因此：

dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])

边界为 dp[i][i] = piles[i]。按区间长度递增填表，可保证转移读取的两个短区间已经完成；最终 dp[0][n - 1] > 0 表示先手获胜。

本题还有更短的数学结论：偶数个位置可分成奇、偶下标两组，先手第一次拿左端或右端就能选择自己要控制的下标奇偶性，此后总能在对手拿完后继续取该组。石子总数为奇数，所以两组之和不相等，先手选择和更大的一组必然超过总数一半，因此本题答案恒为 true。代码仍采用区间 DP，因为它不依赖这些特殊约束，也能直接应对「堆数可为奇数」等面试追问。

解题步骤

创建 dp[n][n]，初始化 dp[i][i] = piles[i]。

枚举区间长度 len = 2..n，再枚举左端点 left，令 right = left + len - 1。

分别计算取左端和取右端后的净分差，取较大值写入 dp[left][right]。

判断完整区间的分差 dp[0][n - 1] 是否为正。

以 [5, 3, 4, 5] 为例：长度为 2 的分差依次为 2、1、1；长度为 3 的两个分差均为 4。最终：

dp[0][3] = max(5 - 4, 5 - 4) = 1

先手最多领先 1 分，因此返回 true。减号的含义是「剩余区间中对手的优势，就是当前玩家的劣势」，不能写成加号。

代码实现

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }
        for (int len = 2; len <= n; len++) {
            for (int left = 0; left + len - 1 < n; left++) {
                int right = left + len - 1;

                int takeLeft = piles[left] - dp[left + 1][right];
                int takeRight = piles[right] - dp[left][right - 1];
                dp[left][right] = Math.max(takeLeft, takeRight);
            }
        }
        return dp[0][n - 1] > 0;
    }
}

func stoneGame(piles []int) bool {
    n := len(piles)
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
        dp[i][i] = piles[i]
    }
    for length := 2; length <= n; length++ {
        for left := 0; left+length-1 < n; left++ {
            right := left + length - 1

            takeLeft := piles[left] - dp[left+1][right]
            takeRight := piles[right] - dp[left][right-1]
            if takeLeft > takeRight {
                dp[left][right] = takeLeft
            } else {
                dp[left][right] = takeRight
            }
        }
    }
    return dp[0][n-1] > 0
}

复杂度分析

时间复杂度：$O(n^2)$。共有 $n(n + 1) / 2$ 个区间，每个区间只比较两种决策。

空间复杂度：$O(n^2)$。保存所有区间状态；可滚动压缩到 $O(n)$，但二维表更直接地对应状态定义。

若只利用本题的奇偶下标必胜结论，时间和额外空间都为 $O(1)$。

关键点总结

两端操作意味着剩余状态始终是连续区间，这是区间 DP 的识别信号。

零和博弈优先记录「当前玩家相对对手的最优分差」，换手后通过减法完成视角转换。

状态依赖两个长度少 1 的区间，所以必须按区间长度递增计算。

return true 的数学解只对本题「堆数为偶数、总数为奇数」的约束成立；区间 DP 则适用于更一般的两端取数问题。

易错点总结

状态含义混入固定玩家：递推中的 dp[i][j] 主语是「当前行动方」，不是始终指 Alex；否则换手后的减法无法成立。

把减号写成加号：piles[i] + dp[i + 1][j] 把对手的优势也算给了自己，得到的既不是分差也不是当前玩家总得分。

左右分支删错区间：取左后应读取 [i + 1, j]，取右后应读取 [i, j - 1]。

不初始化单点区间：只剩一堆时分差应为该堆石子数；默认 0 会让长度为 2 的状态开始就出错。

按左端点正序填表：可能在计算 [i, j] 时读到尚未完成的 [i + 1, j]；按长度递增最稳妥。

把奇偶策略当成通用结论：若堆数改为奇数，两端初始下标奇偶性相同，先手无法任选一组，return true 不再有保证。

相似题目

题目	难度	考察点
486. 预测赢家	中等	去掉偶数堆与总和为奇数的约束，可能平局，判定要改成 `>= 0`
1690. 石子游戏 VII	中等	得分不是取走的那堆，而是取走后剩余区间之和，转移需配合前缀和
312. 戳气球	困难	同为区间 DP 但要枚举「最后戳破」的分割点，多一层循环变成 $O(n^3)$
1000. 合并石头的最低成本	困难	区间 DP 加一维「合并成几堆」，枚举分割点时步长要按 `k - 1` 跳
516. 最长回文子序列	中等	非博弈的区间 DP，转移看两端字符是否相等，可用来纯粹练枚举顺序
面试题 08.14. 布尔运算	中等	区间 DP 上再挂一维真假状态，按运算符合并左右子区间的方案数
464. 我能赢吗	中等	剩余状态不再是连续区间而是任意子集，只能用状态压缩加记忆化搜索
292. Nim 游戏	简单	纯必胜态推导，一行取模即可，用来对照「结论型博弈」与「DP 型博弈」的差别
887. 鸡蛋掉落	困难	极小化极大而非双人博弈，最优决策来自对最坏情况取最小
1043. 分隔数组以得到最大和	中等	线性 DP 加限长回看，说明「分段决策」不一定都要开二维区间表