Nim 游戏 图解题解
这道题到底在问什么
- 输入
- n = 4
- 输出
- false（你先手必输）
- 输入
- n = 1
- 输出
- true（直接拿走 1 颗就赢）
最优解：一步一步想明白
- 3核心就一句话：能一步走到对手的「必输局」，我就赢。下面每一帧都在给一个石子数判 W 还是 L。
- 4先定下出发点：剩 0 颗时轮到我，说明最后一颗已被对手拿走，我输了。所以 0 颗标 L（标红的就是它）。
- 5现在判「剩 1 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 0 颗这几种。看这几格里有没有红色的 L。
- 6三个去向里有红色的「0 颗」是 L，我只要拿走 1 颗，就把这个必输局留给对手，所以剩 1 颗时我能赢，标 W（绿）。
- 7现在判「剩 2 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 1、0 颗这几种。看这几格里有没有红色的 L。
- 8三个去向里有红色的「0 颗」是 L，我只要拿走 2 颗，就把这个必输局留给对手，所以剩 2 颗时我能赢，标 W（绿）。
- 9现在判「剩 3 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 2、1、0 颗这几种。看这几格里有没有红色的 L。
- 10三个去向里有红色的「0 颗」是 L，我只要拿走 3 颗，就把这个必输局留给对手，所以剩 3 颗时我能赢，标 W（绿）。
- 11现在判「剩 4 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 3、2、1 颗这几种。看这几格里有没有红色的 L。
- 12三个去向「3、2、1 颗」全是绿的 W，不管我拿几颗，对手接手都能赢，所以剩 4 颗我必输，标 L（红）。
- 13现在判「剩 5 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 4、3、2 颗这几种。看这几格里有没有红色的 L。
- 14三个去向里有红色的「4 颗」是 L，我只要拿走 1 颗，就把这个必输局留给对手，所以剩 5 颗时我能赢，标 W（绿）。
- 15现在判「剩 6 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 5、4、3 颗这几种。看这几格里有没有红色的 L。
- 16三个去向里有红色的「4 颗」是 L，我只要拿走 2 颗，就把这个必输局留给对手，所以剩 6 颗时我能赢，标 W（绿）。
- 17现在判「剩 7 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 6、5、4 颗这几种。看这几格里有没有红色的 L。
- 18三个去向里有红色的「4 颗」是 L，我只要拿走 3 颗，就把这个必输局留给对手，所以剩 7 颗时我能赢，标 W（绿）。
- 19现在判「剩 8 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 7、6、5 颗这几种。看这几格里有没有红色的 L。
- 20三个去向「7、6、5 颗」全是绿的 W，不管我拿几颗，对手接手都能赢，所以剩 8 颗我必输，标 L（红）。
- 21现在判「剩 9 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 8、7、6 颗这几种。看这几格里有没有红色的 L。
- 22三个去向里有红色的「8 颗」是 L，我只要拿走 1 颗，就把这个必输局留给对手，所以剩 9 颗时我能赢，标 W（绿）。
- 23现在判「剩 10 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 9、8、7 颗这几种。看这几格里有没有红色的 L。
- 24三个去向里有红色的「8 颗」是 L，我只要拿走 2 颗，就把这个必输局留给对手，所以剩 10 颗时我能赢，标 W（绿）。
- 25现在判「剩 11 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 10、9、8 颗这几种。看这几格里有没有红色的 L。
- 26三个去向里有红色的「8 颗」是 L，我只要拿走 3 颗，就把这个必输局留给对手，所以剩 11 颗时我能赢，标 W（绿）。
- 27现在判「剩 12 颗」是输是赢。我能拿 1 到 3 颗，于是能把局面甩给对手——剩 11、10、9 颗这几种。看这几格里有没有红色的 L。
- 28三个去向「11、10、9 颗」全是绿的 W，不管我拿几颗，对手接手都能赢，所以剩 12 颗我必输，标 L（红）。
- 29全部推完，回头看红格：0、4、8、12——清一色 4 的倍数。所以结论是：n 是 4 的倍数就先手必输，否则必赢，一行判断 n % 4 != 0 就够了。
⚠️ 容易写错的地方
✗ 错：真去写 1~3 颗的递归 / DP 数组
✓ 对：先打表找规律，发现答案只看 n % 4
递归会指数爆炸、DP 数组也白开 O(n) 空间；本题规律是 O(1) 的
✗ 错：把 0 颗当成赢
✓ 对：剩 0 颗轮到我 = 上一颗被对手拿走 = 我已输，标 L
基例搞反，整张表的 W/L 会全部反过来
✗ 错：以为先手永远赢
✓ 对：n 为 4 的倍数时先手必输
无论先手拿 1/2/3 颗，对手总能补成 4，把 4 的倍数这个必输局还给你
完整代码（Python / C++ / Java）
Python
def canWinNim(n: int) -> bool:
# n 是 4 的倍数 → 先手必输；否则必赢
return n % 4 != 0C++
bool canWinNim(int n) {
// 4 的倍数先手必输，否则必赢
return n % 4 != 0;
}Java
public boolean canWinNim(int n) {
// 4 的倍数先手必输，否则必赢
return n % 4 != 0;
}复杂度
时间
O(1)
只做一次取余判断，和 n 多大无关
空间
O(1)
不开数组、不递归，只用常数变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 Nim 游戏 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 0 颗标成 L（输）而不是 W？+
剩 0 颗时轮到我，意味着最后一颗已经被对手拿走了，按规则拿到最后一颗的人赢，所以此刻是我输，标 L。这是整张表的基例。
如果每次能拿 1 到 m 颗，规律怎么变？+
基例不变，必输局变成「(m+1) 的倍数」。因为先手拿 x 颗，对手补 (m+1)-x 颗，每回合凑满 m+1。本题 m=3，所以是 4 的倍数。
能不能不打表、直接想出 n % 4？+
可以：抓住对手的「补满 4」策略即可——只要 n 是 4 的倍数，对手总能维持这个倍数把你逼到 0；否则先手第一步先把多出来的余数拿掉，反过来逼对手，于是 n % 4 != 0 即赢。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 Nim 游戏 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。