LeetCode 292. Nim 游戏
目录
题目描述
题意分析
桌上有一堆共
n块石头，你和朋友轮流拿，每次可以拿走 1 块、2 块或 3 块，拿走最后一块石头的人获胜。你先手，双方都采取最优策略，问你能否获胜。「双方都发挥最佳水平」是博弈题的标准前提，它的含义很具体：胜负完全由局面本身决定，不存在运气或对手失误，因此答案是关于
n的一个确定函数。「拿走最后一块的人获胜」等价于「轮到自己时面对 0 块石头的人失败」。把胜负条件翻译成「面对某个数量的一方是赢是输」，是分析这类问题的第一步。
数据范围是最强的信号：
n可以取到 $2^{31} - 1$。这直接排除了逐项递推打表和任何模拟走子的方案，说明必须找到一个闭式结论。边界是最小的几个取值：
n为 1、2、3 时一次就能拿完，必胜；n = 4是第一个必败的局面，也是整个规律的起点。
解法：数学结论
核心思路
先按博弈题的标准套路建立递推。记
f[i]表示「轮到自己且面前有i块石头时，自己是否必胜」。终止态是f[0] = false——没有石头可拿，说明上一步对手已经拿走了最后一块，自己输。对于i >= 1，只要能拿走 1、2 或 3 块之后把一个必败局面丢给对手，自己就赢，于是f[i] = !f[i-1] || !f[i-2] || !f[i-3]（下标为负的项视为不可选）。按这个式子手工推前几项：
f[0] = false，f[1] = f[2] = f[3] = true（一口气拿完），f[4] = !f[3] || !f[2] || !f[1] = false，f[5] = f[6] = f[7] = true（先拿掉余数，把 4 丢给对手），f[8] = false。规律已经浮现：f[i]为假当且仅当i是 4 的倍数。递推本身的瓶颈在于必须从 0 一路算到
n，而n高达二十亿，无论用数组还是滚动变量都跑不完。把规律提炼成不变量就能一步到位：面对 4 的倍数且轮到自己行动的一方必败。理由是对手可以维持这个性质——自己拿走 $k$ 块（$k \in {1,2,3}$），对手立刻拿走 $4 - k$ 块，两人合计恰好消耗 4 块，于是自己再次面对一个 4 的倍数。石头总量严格递减，最终必然落到面对 0 块的局面，也就是输。
反过来，若
n不是 4 的倍数，先手只要第一步拿掉余数n % 4（余数只可能是 1、2、3，都在允许范围内），就把「面对 4 的倍数」这个必败身份转嫁给对手，此后按同样的补足策略应对即可。因此答案就是n % 4 != 0。
解题步骤
- 计算
n对 4 取余。模数取 4 是因为每次可拿的最大数量是 3，双方一来一回可以稳定凑出 $3 + 1 = 4$ 这个固定步长，4 正是这个游戏的周期。- 若余数为 0，说明先手一上来就站在必败位置：无论拿几块，对手都能补足到 4 把局面原样还回来，返回
false。- 若余数不为 0，先手第一步拿走这个余数即可让对手陷入必败位置，返回
true。余数落在 1 到 3 之间，恰好是合法的取法，这一步永远可行。- 整个判断压缩成一次取模，不需要任何循环或递归。
以
n = 7走一遍：$7 \bmod 4 = 3$，非 0，返回true。对应的实际下法是：先手拿 3 块，剩 4 块交给对手。此时对手若拿 1 块剩 3，先手拿 3 块取胜；对手若拿 2 块剩 2，先手拿 2 块取胜；对手若拿 3 块剩 1，先手拿 1 块取胜。三条分支都由先手拿到最后一块，结论成立。再看n = 8：$8 \bmod 4 = 0$，返回false。先手无论拿 $k$ 块，剩下 $8 - k \in {5, 6, 7}$，对手补拿 $4 - k$ 块使剩余变成 4；先手再拿 $k'$ 块，对手再补 $4 - k'$ 块，剩余归零，最后一块被对手拿走，先手确实必败。
代码实现
class Solution {
// 如果先手面对 4 的倍数，无论拿 1、2、3 块，对手都能补到 4，让先手再次面对 4 的倍数。
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}
func canWinNim(n int) bool {
// 如果先手面对 4 的倍数，无论拿 1、2、3 块，对手都能补到 4，让先手再次面对 4 的倍数。
return n%4 != 0
}
复杂度分析
- 时间复杂度：$O(1)$，只做一次取模和一次比较，与
n的大小无关。- 空间复杂度：$O(1)$，没有数组、没有递归栈，连临时变量都不需要。
关键点总结
- 博弈题的通用起手式是从终止态倒推：先明确「什么局面轮到谁就是输」，再用「能否一步走到必败局面」定义必胜局面。有了这个框架，规律是被推出来的而不是猜出来的。
- 每轮取 1 到 $m$ 个、取走最后一个者胜的取石子游戏（Bash 博弈）通解是
n mod (m + 1)：余数非 0 时先手必胜，且第一步就是拿掉余数。本题是 $m = 3$ 的特例。- 「补足到固定步长」是维持不变量的经典手段。对手每次的应对都由自己的动作唯一确定，这种成对策略保证了必败性质在整局中一直成立。
- 数据范围到 $2^{31}$ 是「必须找闭式解」的明确信号。看到范围就该放弃递推，转而打小表找周期。
- 面试视角：千万不要上来就甩出
n % 4 != 0，那会被认为是背题。正确的表达顺序是：写出递推式、手推前八项、指出周期为 4、给出「补足到 4」的策略证明，最后才落到一行代码。过程远比结论值钱。- 面试视角：常见追问有两类。改成「每次取 1 到 $m$ 个」，答
n mod (m + 1)；改成「每次可取的数量限定在某个集合内」，就要说明一般情形需要 Sprague-Grundy 定理计算 SG 值，简单取模不再适用。能划出结论的适用边界，比会用结论更重要。
易错点总结
- 错误写法：把判据方向写反，返回
n % 4 == 0。用例n = 4→ 返回true，而先手面对 4 的倍数必败，正确答案是false。- 错误写法：老老实实开数组做递推。用例
n = 2147483647→ 需要长度二十一亿的布尔数组，内存直接溢出；即便换成滚动变量，循环次数同样跑不完。- 错误写法：用递归实现
f[i] = !f[i-1] || !f[i-2] || !f[i-3]且不加记忆化。用例n = 50→ 搜索树呈指数级膨胀，直接超时。- 错误写法：把胜负条件理解反，当成「拿走最后一块的人输」。用例
n = 1→ 按反向规则先手被迫拿走唯一一块而告负，返回false，本题的正确答案是true。- 错误写法：凭直觉认为石头越多先手越有利，写成
n > 3。用例n = 1→ 返回false，正确答案是true；用例n = 8→ 返回true，正确答案是false。- 错误写法：把模数取成 3，误以为「每次最多拿 3 个」就该模 3。用例
n = 3→3 % 3 == 0使函数返回false，而先手一次拿完即胜，正确答案是true。- 错误写法：把结论记成「偶数必败、奇数必胜」。用例
n = 2→ 返回false，正确答案是true；周期是 4 而不是 2。- 错误写法：在代码里真的模拟双方轮流取石子的过程。用例
n = 1000000→ 即使每一步都是常数时间，也要循环上百万次；更要命的是模拟时还得自己写对「补足到 4」的应对策略，一旦写错就会得到与结论不一致的答案。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 877. 石子游戏 | 中等 | 从两端取石子且石子有数值，需要区间动态规划或先手占位的奇偶论证 |
| 486. 预测赢家 | 中等 | 同为两端取数博弈，但要计算最终分差而非单纯胜负 |
| 1690. 石子游戏 VII | 中等 | 得分由剩余石子总和决定，区间 DP 的状态是分差，需要前缀和配合 |
| 1227. 飞机座位分配概率 | 中等 | 同样是把一个看似复杂的随机过程压成常数时间结论，靠对称性而非博弈分析 |