拿糖果这个题我在各种OJ和比赛里见到过好几个变体核心都是同一个博弈模型。很多人在“算法提高”这类题目上卡住并不是代码不会写而是没把这层博弈关系想透。今天我就拿最典型的一个版本——糖果堆一共 n 个两人轮流拿每次可以拿 1、3、4 颗拿到最后一颗的人获胜——把从读题到AC的完整链路拆一遍。这题适合算法刚入门的读者也适合准备竞赛但总觉得博弈题“靠感觉”的人。看懂这套必胜态/必败态的推导方法以后再遇到“拿石子”“拿硬币”“拿纸牌”本质都一样换层皮而已。而且我会把空间优化、周期发现这些实战技巧也放进来这些恰恰是普通题解里讲得最少、但比赛里最能拉开差距的东西。1. 题目分析与博弈模型定位1.1 先把题意吃透题目参数很简单n 颗糖果每次操作拿 1、3、4 颗拿完最后一颗的人赢双方都最优问先手必胜还是必败。很多初学者一上来就想着模拟“你一步我一步”的游戏过程试图从先手视角枚举所有可能性这是最大的误区。n 小的时候枚举勉强可行n 一旦到 10^5、10^9这种思路立刻报废。正确的做法是把它抽象成“状态 状态转移”的问题。这里的状态只有一个维度当前剩余糖果数。每个状态有一个属性——对“轮到走棋的人”来说这个状态是必胜还是必败。注意这个属性的主语是回合玩家不是先手或后手这是理解博弈DP的关键。当你站在某个状态下思考时你根本不关心之前是谁拿的、拿了多少只关心当前局面和自己能做的选择。1.2 为什么这属于“公平组合博弈”公平组合博弈Impartial Combinatorial Game有三个特征两个人能做的操作完全相同、没有随机性、没有隐藏信息。拿糖果完美符合。这类博弈最核心的结论是任何一个状态要么是必胜态要么是必败态没有中间地带。判断标准就一句话一个状态是必败态当且仅当它的所有后继状态都是必胜态一个状态是必胜态当且仅当存在至少一个后继状态是必败态。这句话值得反复琢磨。它的本质是“把包袱甩给对方”——我能走到一个让对方必输的局面那我就赢了。这也解释了为什么双方都“最优”的时候胜负其实在游戏开始前就已经由 n 决定了。听起来有点宿命论但算法题确实就是这么残酷先手赢不赢跟运气没半点关系只取决于 n 落在哪个状态。2. 状态设计与手算推演2.1 定义 dp 数组用 dp[i] 表示剩余 i 颗糖果时当前回合玩家是否必胜。那么dp[0] false因为已经没糖果可拿了而这个局面出现说明上一手的人刚拿走了最后一颗当前玩家直接输。转移dp[i] true如果存在某个合法拿取数 m ∈ {1, 3, 4}使得 i - m 0 且 dp[i - m] false。因为这样你拿完之后对方面对的就是必败态。如果所有合法转移都导向 dp[i - m] true那 dp[i] false因为你无论怎么拿对方都在赢的局面里。这里的“为什么”特别值得说清楚我们在判断 dp[i] 时目光不是盯着自己下一步能拿到多少而是盯着“我把局面变成什么样对方就难搞了”。这是一种典型的逆向思维。很多人第一版代码写成“能拿就走走到最后糖果多的人赢”完全不对因为游戏目标是拿最后一颗不是比累计数量。2.2 从小规模推起从 i 0 开始一个个推i 0false边界。i 1拿 1 后剩 0dp[0] false所以 dp[1] true。i 2只能拿 1拿 3/4 超了拿完剩 1dp[1] true所以 dp[2] false。i 3拿 1 → 剩 2false可行拿 3 → 剩 0false也可行所以 dp[3] true。i 4拿 1 → 3true拿 3 → 1true拿 4 → 0false可行所以 dp[4] true。继续推到 n 14把结果列成表i01234567891011121314dp[i]输赢输赢赢赢赢输赢输赢赢赢赢输看到规律没有从 i 0 到 i 6 是“输赢输赢赢赢赢”从 i 7 到 i 13 又是完全一样的“输赢输赢赢赢赢”。周期是 7。也就是说所有必败态都满足 i % 7 0 或 i % 7 2。这个发现不是巧合是博弈DP的周期性后面我会专门讲怎么利用它。3. 核心代码实现与逐行拆解3.1 最朴素的 DP 写法先把最直观的版本写出来保证思路正确是第一位def can_first_win(n: int) - bool: moves [1, 3, 4] dp [False] * (n 1) for i in range(1, n 1): for m in moves: if i - m 0 and not dp[i - m]: dp[i] True break return dp[n]逐行解释dp [False] * (n 1)初始化全部为 false。这样 dp[0] 天然就是 false符合边界定义。外层循环从小到大枚举剩余数量保证算 dp[i] 时 dp[i-1]、dp[i-3]、dp[i-4] 都已经算好了。这依赖动态规划的“无后效性”——过去的状态不会因为未来怎么走而改变。内层循环枚举三种拿法一旦找到一个合法的、且对方会输的局面立刻把 dp[i] 置为 true 并跳出。这个break很关键它体现的是“存在即可赢”不用把三种拿法全遍历完。i - m 0这个判断不能省。i 很小的时候比如 i 2拿 3、拿 4 都是非法的。忘了判断的话Python 里会出现负数索引悄悄从数组尾部取值结果错得莫名其妙——这个坑我下面细说。这段代码的时间复杂度 O(n * k)k 是拿取方案数此处为 3空间复杂度 O(n)。如果你在蓝桥杯或者某些 OJ 上看到 n 不超过 10000这个版本直接交就完了。但要是 n 上了 10^9O(n) 必炸。3.2 C 版本竞赛常用 C给一版同样逻辑的#include iostream #include vector using namespace std; int main() { long long n; cin n; if (n% 7 0 || n % 7 2) { cout NO endl; } else { cout YES endl; } return 0; }等等这里我直接跳到了周期结论。别急如果题目 n 范围小老老实实写 DP 就够#include iostream #include vector using namespace std; int main() { int n; cin n; vectorbool dp(n 1, false); int moves[3] {1, 3, 4}; for (int i 1; i n; i) { for (int j 0; j 3; j) { if (i - moves[j] 0 !dp[i - moves[j]]) { dp[i] true; break; } } } cout (dp[n] ? YES : NO) endl; return 0; }这个版本好理解但存在一个隐藏问题n 输入很大的时候vectorbool虽然按位存储省空间但时间复杂度依然 O(n)。真正的优化得靠下一节说的周期规律。4. 周期发现与 O(1) 解法4.1 为什么会出现周期很多人看到“周期 7”就觉得是玄学其实背后有严谨的数学原理。观察转移方程dp[i] 的值只依赖 dp[i-1]、dp[i-3]、dp[i-4]也就是最近的 4 个状态。拿当前的“最近 4 个状态”拼成一个四元组比如 (dp[i-4], dp[i-3], dp[i-2], dp[i-1])每个元素只有 true/false 两种所以四元组最多只有 2^4 16 种可能。根据抽屉原理计算过程中一定会出现两个相同的四元组。一旦相邻的四元组重复了后面所有状态就都会按同样的节奏重复因为转移规则是确定性的——相同的“昨天”必然推出相同的“今天”。这就是周期必然出现的数学保证。对于 {1, 3, 4} 这个拿取集合实际周期比 16 还短只需要 7 步就循环了。这个套路在博弈题里非常实用。你不一定每次都能一眼看出周期但可以程序化地找先算前 50 个 dp 值肉眼扫一遍发现重复片段就验证几轮确认无误后再上 O(1) 公式。我处理陌生博弈题时第一步永远是打表第二步才是猜结论。4.2 利用周期写出最优解对于 {1, 3, 4}必败态满足 n % 7 ∈ {0, 2}所以最终代码就一行判断def can_first_win(n: int) - bool: return n % 7 not in (0, 2)优势是时间 O(1)空间 O(1)。n 不管多大哪怕是 10^18一个取模就出结果。这里有一个重要提醒如果你是用“打表找周期”的方式得到结论在正式提交前最好多验证几个 n。我一般会写个随机测试用朴素 DP 和 O(1) 公式同时跑 100 组随机数据对比结果一致才放心。打表发现规律是猜测对拍验证才是证明。竞赛里因为周期找错或者边界条件漏判而白丢分的选手我见过太多了。4.3 特殊变体每次拿 1~m 颗如果题目改成“每次可以拿 1 到 m 颗”同样可以用 DP但结论更简单必败态是 (m1) 的倍数所以先手必胜当且仅当 n % (m1) ! 0。这个结论怎么来的因为 (m1) 颗糖果时无论先手拿几颗设为 x后手都可以补上 (m1 - x) 颗把局面重新变成 (m1) 的倍数交给先手。这是经典的“镜像策略”。对比一下两种规则的区别{1,3,4} 的必败态不是简单等距分布而是模 7 余 0 或 2 交替出现{1,2} 则是模 3 余 0 一个点。所以遇到博弈题永远不要想当然套固定公式老老实实从 DP 出发推导。5. 踩坑实录与扩展方向5.1 最容易翻车的几个点第一边界下意识手滑。dp[0] 的值是整道题的地基它错了后面全错。实际做题时有人把 dp[0] 写成 true理由是“0 颗糖果代表拿到了最后一颗所以赢”——这是站在已经赢了的玩家视角而不是“轮到谁走”的视角。请记住定义dp[i] 是“剩余 i 颗且轮到当前玩家走”时当前玩家的胜败。此时 i0 意味着无棋可走当前玩家铁定输。第二负数索引。Python 的列表支持负索引这是个温柔陷阱。i2 时如果没判断i-m 0直接访问 dp[2-4] 拿到的是 dp[-2]也就是数组倒数第二个元素那个值完全不知道是谁结果必然错乱。这种 bug 编译器不报错肉眼不容易发现最好的防御就是一开始就写好完整判断。第三转移条件的逻辑写反。正确条件是“存在一个后继是必败态”。新手容易写成“所有后继都是必败态”那只有在极端情况下才成立大多数时候会把必胜态错判成必败态。写代码时一定要用any或break表达“存在”语义而不是“所有”语义。第四混淆“拿取数量”和“必胜判断”。在 {1,3,4} 里每次能拿 1、3、4但必胜判断不是看当前剩余糖果能不能被 4 或 3 整除而是看模 7 的余数。统计值不等于规律值这也是为什么必须从状态转移推而不是凭直觉猜。5.2 一套可复用的通用模版无论拿取集合是什么核心 DP 骨架都一样。我更常写的是下面这个通用版本把 move 集合作为参数传入def solve_coin_game(n: int, moves: list[int]) - bool: dp [False] * (n 1) for i in range(1, n 1): for m in moves: if i - m 0 and not dp[i - m]: dp[i] True break return dp[n]这段代码适用于任意拿取集合。它的本质和完全背包、硬币问题的状态设计有异曲同工之妙——都是“当前状态由前置若干状态推出”区别只在于转移时的逻辑是“存在必败”而非“累计最大值”。5.3 还能怎么扩展拿糖果只是最原始的入门模型。进阶方向至少有三个多堆糖果局面变成多个维度这时要引入尼姆和Nim-sum或 SG 函数每堆单独算 SG 值再异或非零则先手胜。拿糖果的 SG 函数就是 mex{后继 SG 值}而 dp 数组里的胜败关系只是 SG 值为 0 与否的特例。拿最后一颗输的变体Misère 规则边界情况和普通版不同必败态的判定会改变。特别是当所有状态只能拿 1 颗时胜负完全反转。带限制的拿取比如“当前拿取数量不能等于对手上次拿取的数量”。这会让状态维度从一维变二维必须把上次拿的数也纳入状态。这种题在面试里也常见思路依旧是“加维度、扩 DP”。我在实际刷题中最大的体会是博弈题不怕条件复杂就怕你一开始就陷入“模拟双方操作”的递归深渊。把状态定义清楚、转移逻辑写成“是否存在一个把对方送到必败态的选择”十道博弈题九道都能顺利解出来。剩下一道大概率是状态压缩或者 SG 函数的问题但底层思路依然没变。最后分享一个小技巧做完这道题不妨把 moves 改成 {1, 2, 6}、{3, 5, 7} 之类的集合自己打表看看周期怎么变。多测几组你对“周期必然存在”的直觉会牢固很多以后遇到陌生的博弈题第一步打表找规律就会成为肌肉记忆。这个习惯比多背几道模板题有用得多。
拿糖果这个题我在各种OJ和比赛里见到过好几个变体核心都是同一个博弈模型。很多人在“算法提高”这类题目上卡住并不是代码不会写而是没把这层博弈关系想透。今天我就拿最典型的一个版本——糖果堆一共 n 个两人轮流拿每次可以拿 1、3、4 颗拿到最后一颗的人获胜——把从读题到AC的完整链路拆一遍。这题适合算法刚入门的读者也适合准备竞赛但总觉得博弈题“靠感觉”的人。看懂这套必胜态/必败态的推导方法以后再遇到“拿石子”“拿硬币”“拿纸牌”本质都一样换层皮而已。而且我会把空间优化、周期发现这些实战技巧也放进来这些恰恰是普通题解里讲得最少、但比赛里最能拉开差距的东西。1. 题目分析与博弈模型定位1.1 先把题意吃透题目参数很简单n 颗糖果每次操作拿 1、3、4 颗拿完最后一颗的人赢双方都最优问先手必胜还是必败。很多初学者一上来就想着模拟“你一步我一步”的游戏过程试图从先手视角枚举所有可能性这是最大的误区。n 小的时候枚举勉强可行n 一旦到 10^5、10^9这种思路立刻报废。正确的做法是把它抽象成“状态 状态转移”的问题。这里的状态只有一个维度当前剩余糖果数。每个状态有一个属性——对“轮到走棋的人”来说这个状态是必胜还是必败。注意这个属性的主语是回合玩家不是先手或后手这是理解博弈DP的关键。当你站在某个状态下思考时你根本不关心之前是谁拿的、拿了多少只关心当前局面和自己能做的选择。1.2 为什么这属于“公平组合博弈”公平组合博弈Impartial Combinatorial Game有三个特征两个人能做的操作完全相同、没有随机性、没有隐藏信息。拿糖果完美符合。这类博弈最核心的结论是任何一个状态要么是必胜态要么是必败态没有中间地带。判断标准就一句话一个状态是必败态当且仅当它的所有后继状态都是必胜态一个状态是必胜态当且仅当存在至少一个后继状态是必败态。这句话值得反复琢磨。它的本质是“把包袱甩给对方”——我能走到一个让对方必输的局面那我就赢了。这也解释了为什么双方都“最优”的时候胜负其实在游戏开始前就已经由 n 决定了。听起来有点宿命论但算法题确实就是这么残酷先手赢不赢跟运气没半点关系只取决于 n 落在哪个状态。2. 状态设计与手算推演2.1 定义 dp 数组用 dp[i] 表示剩余 i 颗糖果时当前回合玩家是否必胜。那么dp[0] false因为已经没糖果可拿了而这个局面出现说明上一手的人刚拿走了最后一颗当前玩家直接输。转移dp[i] true如果存在某个合法拿取数 m ∈ {1, 3, 4}使得 i - m 0 且 dp[i - m] false。因为这样你拿完之后对方面对的就是必败态。如果所有合法转移都导向 dp[i - m] true那 dp[i] false因为你无论怎么拿对方都在赢的局面里。这里的“为什么”特别值得说清楚我们在判断 dp[i] 时目光不是盯着自己下一步能拿到多少而是盯着“我把局面变成什么样对方就难搞了”。这是一种典型的逆向思维。很多人第一版代码写成“能拿就走走到最后糖果多的人赢”完全不对因为游戏目标是拿最后一颗不是比累计数量。2.2 从小规模推起从 i 0 开始一个个推i 0false边界。i 1拿 1 后剩 0dp[0] false所以 dp[1] true。i 2只能拿 1拿 3/4 超了拿完剩 1dp[1] true所以 dp[2] false。i 3拿 1 → 剩 2false可行拿 3 → 剩 0false也可行所以 dp[3] true。i 4拿 1 → 3true拿 3 → 1true拿 4 → 0false可行所以 dp[4] true。继续推到 n 14把结果列成表i01234567891011121314dp[i]输赢输赢赢赢赢输赢输赢赢赢赢输看到规律没有从 i 0 到 i 6 是“输赢输赢赢赢赢”从 i 7 到 i 13 又是完全一样的“输赢输赢赢赢赢”。周期是 7。也就是说所有必败态都满足 i % 7 0 或 i % 7 2。这个发现不是巧合是博弈DP的周期性后面我会专门讲怎么利用它。3. 核心代码实现与逐行拆解3.1 最朴素的 DP 写法先把最直观的版本写出来保证思路正确是第一位def can_first_win(n: int) - bool: moves [1, 3, 4] dp [False] * (n 1) for i in range(1, n 1): for m in moves: if i - m 0 and not dp[i - m]: dp[i] True break return dp[n]逐行解释dp [False] * (n 1)初始化全部为 false。这样 dp[0] 天然就是 false符合边界定义。外层循环从小到大枚举剩余数量保证算 dp[i] 时 dp[i-1]、dp[i-3]、dp[i-4] 都已经算好了。这依赖动态规划的“无后效性”——过去的状态不会因为未来怎么走而改变。内层循环枚举三种拿法一旦找到一个合法的、且对方会输的局面立刻把 dp[i] 置为 true 并跳出。这个break很关键它体现的是“存在即可赢”不用把三种拿法全遍历完。i - m 0这个判断不能省。i 很小的时候比如 i 2拿 3、拿 4 都是非法的。忘了判断的话Python 里会出现负数索引悄悄从数组尾部取值结果错得莫名其妙——这个坑我下面细说。这段代码的时间复杂度 O(n * k)k 是拿取方案数此处为 3空间复杂度 O(n)。如果你在蓝桥杯或者某些 OJ 上看到 n 不超过 10000这个版本直接交就完了。但要是 n 上了 10^9O(n) 必炸。3.2 C 版本竞赛常用 C给一版同样逻辑的#include iostream #include vector using namespace std; int main() { long long n; cin n; if (n% 7 0 || n % 7 2) { cout NO endl; } else { cout YES endl; } return 0; }等等这里我直接跳到了周期结论。别急如果题目 n 范围小老老实实写 DP 就够#include iostream #include vector using namespace std; int main() { int n; cin n; vectorbool dp(n 1, false); int moves[3] {1, 3, 4}; for (int i 1; i n; i) { for (int j 0; j 3; j) { if (i - moves[j] 0 !dp[i - moves[j]]) { dp[i] true; break; } } } cout (dp[n] ? YES : NO) endl; return 0; }这个版本好理解但存在一个隐藏问题n 输入很大的时候vectorbool虽然按位存储省空间但时间复杂度依然 O(n)。真正的优化得靠下一节说的周期规律。4. 周期发现与 O(1) 解法4.1 为什么会出现周期很多人看到“周期 7”就觉得是玄学其实背后有严谨的数学原理。观察转移方程dp[i] 的值只依赖 dp[i-1]、dp[i-3]、dp[i-4]也就是最近的 4 个状态。拿当前的“最近 4 个状态”拼成一个四元组比如 (dp[i-4], dp[i-3], dp[i-2], dp[i-1])每个元素只有 true/false 两种所以四元组最多只有 2^4 16 种可能。根据抽屉原理计算过程中一定会出现两个相同的四元组。一旦相邻的四元组重复了后面所有状态就都会按同样的节奏重复因为转移规则是确定性的——相同的“昨天”必然推出相同的“今天”。这就是周期必然出现的数学保证。对于 {1, 3, 4} 这个拿取集合实际周期比 16 还短只需要 7 步就循环了。这个套路在博弈题里非常实用。你不一定每次都能一眼看出周期但可以程序化地找先算前 50 个 dp 值肉眼扫一遍发现重复片段就验证几轮确认无误后再上 O(1) 公式。我处理陌生博弈题时第一步永远是打表第二步才是猜结论。4.2 利用周期写出最优解对于 {1, 3, 4}必败态满足 n % 7 ∈ {0, 2}所以最终代码就一行判断def can_first_win(n: int) - bool: return n % 7 not in (0, 2)优势是时间 O(1)空间 O(1)。n 不管多大哪怕是 10^18一个取模就出结果。这里有一个重要提醒如果你是用“打表找周期”的方式得到结论在正式提交前最好多验证几个 n。我一般会写个随机测试用朴素 DP 和 O(1) 公式同时跑 100 组随机数据对比结果一致才放心。打表发现规律是猜测对拍验证才是证明。竞赛里因为周期找错或者边界条件漏判而白丢分的选手我见过太多了。4.3 特殊变体每次拿 1~m 颗如果题目改成“每次可以拿 1 到 m 颗”同样可以用 DP但结论更简单必败态是 (m1) 的倍数所以先手必胜当且仅当 n % (m1) ! 0。这个结论怎么来的因为 (m1) 颗糖果时无论先手拿几颗设为 x后手都可以补上 (m1 - x) 颗把局面重新变成 (m1) 的倍数交给先手。这是经典的“镜像策略”。对比一下两种规则的区别{1,3,4} 的必败态不是简单等距分布而是模 7 余 0 或 2 交替出现{1,2} 则是模 3 余 0 一个点。所以遇到博弈题永远不要想当然套固定公式老老实实从 DP 出发推导。5. 踩坑实录与扩展方向5.1 最容易翻车的几个点第一边界下意识手滑。dp[0] 的值是整道题的地基它错了后面全错。实际做题时有人把 dp[0] 写成 true理由是“0 颗糖果代表拿到了最后一颗所以赢”——这是站在已经赢了的玩家视角而不是“轮到谁走”的视角。请记住定义dp[i] 是“剩余 i 颗且轮到当前玩家走”时当前玩家的胜败。此时 i0 意味着无棋可走当前玩家铁定输。第二负数索引。Python 的列表支持负索引这是个温柔陷阱。i2 时如果没判断i-m 0直接访问 dp[2-4] 拿到的是 dp[-2]也就是数组倒数第二个元素那个值完全不知道是谁结果必然错乱。这种 bug 编译器不报错肉眼不容易发现最好的防御就是一开始就写好完整判断。第三转移条件的逻辑写反。正确条件是“存在一个后继是必败态”。新手容易写成“所有后继都是必败态”那只有在极端情况下才成立大多数时候会把必胜态错判成必败态。写代码时一定要用any或break表达“存在”语义而不是“所有”语义。第四混淆“拿取数量”和“必胜判断”。在 {1,3,4} 里每次能拿 1、3、4但必胜判断不是看当前剩余糖果能不能被 4 或 3 整除而是看模 7 的余数。统计值不等于规律值这也是为什么必须从状态转移推而不是凭直觉猜。5.2 一套可复用的通用模版无论拿取集合是什么核心 DP 骨架都一样。我更常写的是下面这个通用版本把 move 集合作为参数传入def solve_coin_game(n: int, moves: list[int]) - bool: dp [False] * (n 1) for i in range(1, n 1): for m in moves: if i - m 0 and not dp[i - m]: dp[i] True break return dp[n]这段代码适用于任意拿取集合。它的本质和完全背包、硬币问题的状态设计有异曲同工之妙——都是“当前状态由前置若干状态推出”区别只在于转移时的逻辑是“存在必败”而非“累计最大值”。5.3 还能怎么扩展拿糖果只是最原始的入门模型。进阶方向至少有三个多堆糖果局面变成多个维度这时要引入尼姆和Nim-sum或 SG 函数每堆单独算 SG 值再异或非零则先手胜。拿糖果的 SG 函数就是 mex{后继 SG 值}而 dp 数组里的胜败关系只是 SG 值为 0 与否的特例。拿最后一颗输的变体Misère 规则边界情况和普通版不同必败态的判定会改变。特别是当所有状态只能拿 1 颗时胜负完全反转。带限制的拿取比如“当前拿取数量不能等于对手上次拿取的数量”。这会让状态维度从一维变二维必须把上次拿的数也纳入状态。这种题在面试里也常见思路依旧是“加维度、扩 DP”。我在实际刷题中最大的体会是博弈题不怕条件复杂就怕你一开始就陷入“模拟双方操作”的递归深渊。把状态定义清楚、转移逻辑写成“是否存在一个把对方送到必败态的选择”十道博弈题九道都能顺利解出来。剩下一道大概率是状态压缩或者 SG 函数的问题但底层思路依然没变。最后分享一个小技巧做完这道题不妨把 moves 改成 {1, 2, 6}、{3, 5, 7} 之类的集合自己打表看看周期怎么变。多测几组你对“周期必然存在”的直觉会牢固很多以后遇到陌生的博弈题第一步打表找规律就会成为肌肉记忆。这个习惯比多背几道模板题有用得多。
实现：从slack优化到BFS版完整模板)
的KM算法BFS模板：从顶标到增广全解析)
