1. 初见这道题被“博弈”两个字吓退的选手不在少数LeetCode 1025“除数博弈”在题库里标的是简单难度但不少朋友第一次刷到它时心里都会犯嘀咕题目带着“博弈”字样是不是要用什么复杂的博弈论模型是不是要建一棵庞大的游戏状态树说实话我最初也是抱着这种心态点开题目的结果读完以后发现这道题好玩的地方恰恰在于——它用一个博弈的外壳包裹了一个非常漂亮的数学规律。先把原题摆出来。Alice和Bob轮流玩一个游戏初始给一个正整数 n。每一轮当前玩家要选择一个 x满足 0 x n并且 n 能被 x 整除也就是 n % x 0然后把 n 替换成 n - x。如果哪位玩家轮到自己时无法找到这样的 x那他就输了。题目假定 Alice 先手问给定 nAlice 能否获胜。这个规则初看有一点绕但拆开来说就是你每次必须真的找到一个“真因子”不能等于 n 本身然后把它从 n 里减掉。减完之后新的 n 交给对方。所以每次操作后数字都会严格变小游戏一定会在有限的步数内结束不会出现死循环。我在面试里也问过候选人这道题一个很有意思的现象是基础不错、但没提前刷过这道题的人看到“博弈”两个字后大部分人第一反应是去回溯枚举——把 n 的所有因子找出来然后递归判断对方是否会输。这个思路本身没错但它没有触及这道题真正的考点。如果你只知道暴力递归那这道题做出来不难但你可能错过了一个很漂亮的思维跃迁。这篇文章我会先从最朴素的递归思路说起然后逐步推导到那个“一眼看穿”的奇偶结论。如果你只需要答案一个 if 判断就够了但如果你想把这道题的价值榨干那建议你把推导过程、动态规划写法、以及边界情况都一起过一遍这样遇到同类题目时你就知道该怎么下手了。2. 把游戏规则在纸上推演一遍2.1 从 n 1 开始谁先手谁输我们先别盯着代码拿一张纸从最小的 n 开始推。n 1 时Alice 需要找一个 x满足 0 x 1 且 1 % x 0。看这个条件x 连 1 都取不到因为题目强制要求 x 必须严格小于 n。所以 Alice 没有任何合法操作直接输掉。结论n 1 时先手 Alice 必输。这个“边界条件”是整道题的地基。递归、动态规划、数学推导所有解法都要从这一个小结论出发。很多人在推 n 2 的时候容易出错原因就是忘了 n 1 这个前提导致想当然地推断。2.2 推演 n 2 到 n 7 的结果接下来一个一个推顺便把过程记录下来方便后面找规律。n 2。Alice 可以选择 x 1因为 2 % 1 01 也满足小于 2。执行后 n 变成 1。轮到 Bob 面对 n 1没得选Bob 输。所以 Alice 只要走 x 1就稳赢。结论n 2 时先手 Alice 必赢。n 3。3 的真因子只有 1所以 Alice 只能选 x 1。执行后 n 变成 2轮到 Bob 面对 n 2。而刚才已经推导过了n 2 时是先手Bob必赢。也就是说 Alice 无论怎么走都会把对手送到一个必胜局面。结论n 3 时Alice 必输。n 4。4 的真因子有 1 和 2。先看选 x 1 的情况n 变成 3Bob 面对 n 3。根据上面的推导n 3 是先手必输局所以 Bob 会输Alice 赢。因为 Alice 存在一个能取胜的选择游戏里她当然会选这条路所以结论直接就是 Alice 必赢。n 5。5 是质数真因子只有 1Alice 只能把局面交给 n 4。n 4 是先手必赢局所以 Bob 会赢Alice 必输。n 6。6 的真因子有 1、2、3。Alice 逐个尝试选 x 1n 变成 55 是先手必输局Bob 输Alice 赢。已经找到必胜路线后面的不用看了。 结论n 6 时 Alice 必赢。n 7。7 是质数只能选 x 1n 变成 6。6 是先手必赢局Bob 拿到 6 后必赢所以 Alice 必输。把这些结果整理一下n先手结果1输2赢3输4赢5输6赢7输看到这里结论已经很清晰了从 1 到 7奇数全部是先手输偶数全部是先手赢。那么所有正整数是不是都遵循这个规律直觉告诉我是但要真正下结论还需要一个完整的逻辑论证。光靠归纳几个数是站不住脚的万一 n 9 忽然反水了呢所以下一步我们来证明这个问题。2.3 为什么奇偶性能决定胜负证明过程拆解要证明“n 为偶数时 Alice 赢n 为奇数时 Alice 输”数学上最稳妥的办法是数学归纳法。我之前在刷题笔记里很少写完整证明但这道题我建议你务必自己证一遍因为它的证明过程很简短而且能帮你养成“先证明、后写码”的习惯。命题分两部分。第一部分当 n 为奇数时先手必输。第二部分当 n 为偶数时先手必赢。怎么证关键要弄清楚一件事奇数经过一次合法操作后一定会变成偶数而偶数一定有办法经过一次操作后变成奇数。先看前半句。n 是奇数时它的任何一个真因子 x 也必然是奇数吗想想看奇数不可能有偶因子因为偶数因子乘以任何正整数都能得到偶数结果。所以 n 的因子全是奇数。奇数减奇数等于偶数所以 n 变成偶数。这就意味着如果 Alice 拿到一个奇数她无论怎么操作Bob 拿到的都一定是一个偶数。再看后半句。n 是偶数时x 1 一定是一个合法选择。1 是任何正整数的因子而且一定小于 n前提是 n 1这个后文会细说。偶数减 1 等于奇数所以 Alice 至少可以通过选 x 1让 Bob 面对一个奇数。接下来把这几个事实串起来做归纳。基础情况 n 1 时先手输n 2 时先手赢都已经验证过了。假设对于所有小于 n 的正整数奇数先手输、偶数先手赢都成立。现在考虑 n如果 n 是奇数无论 Alice 怎么选n - x 都是偶数且小于 n。根据归纳假设偶数局面是先手必胜的。所以 Alice 把必胜局面交给了 BobAlice 必输。如果 n 是偶数Alice 选 x 1n 变成奇数 n - 1小于 n。根据归纳假设奇数局面是先手必输的。Bob 面对必输局Bob 输所以 Alice 赢。这样两部分就都证完了。最终结论n 为偶数返回 truen 为奇数返回 false。这个证明的精髓在于它把 Alice 和 Bob 的博弈抽象成两个状态之间的转换奇数状态必然把对手送到偶数状态而偶数状态可以选择把对手送到奇数状态。两个人都足够聪明时谁被迫先手拿到奇数状态谁就注定会输。2.4 一行代码解决最简写法和它为什么可行知道结论后代码反而成了最不重要的部分。用 C、Java、Python 写都只在毫厘之间核心逻辑就是判断奇偶。class Solution: def divisorGame(self, n: int) - bool: return n % 2 0class Solution { public: bool divisorGame(int n) { return n % 2 0; } };有些朋友可能会担心n 2 时选 x 1n 变成 1没问题但如果 n 是更大的偶数比如 n 8只选 x 1 就一定能赢吗用上面的归纳结论看n 8 时选 x 1Bob 拿到 77 是奇数先手必输所以 Alice 当然赢。这个策略是“全局有效”的不只是对前几个数有效。所以这个一行代码不是巧合而是整个数学推导的浓缩。你把这个推导过程写进注释里面试官想追问都问不倒你。3. 动态规划解法不靠数学规律也能正确求解3.1 状态定义与转移方程是怎么来的如果你还没看出奇偶规律或者题目稍加变形导致规律失效了那动态规划就是最稳妥的通用解法。这道题的 DP 思路其实非常直观因为它天然符合“当前局面只取决于后续局面”的博弈结构。定义 dp[i] 表示“数字为 i 时当前轮到的玩家是否必胜”。注意这里不区分是 Alice 还是 Bob因为规则对两个人完全一样谁拿到这个数字谁就拥有同样的胜率前景。这其实就是博弈论里的“公平组合游戏”特征两个人角色对称只有先后手之分。base case 是 dp[1] false因为数字为 1 时当前玩家没有任何合法操作直接输。然后从 i 2 开始向后递推。对于每个 i枚举它的真因子 x如果存在某一个 x 使得 dp[i - x] false那就说明当前玩家可以选择这个 x把对方送到必败局面那么 dp[i] true。如果所有 x 都只能把对方送到必胜局面那 dp[i] false。写成状态转移方程dp[i] OR_{x 是 i 的真因子} ( not dp[i - x] )这个方程描述了一个很朴素的博弈策略我走一步只要让对手处于必败状态我就赢了。3.2 完整实现与复杂度分析枚举因子时不需要把 x 枚举到 i只需要枚举 i 的所有真因子。一般枚举 1 到 sqrt(i) 找约数对也就是同时处理 x 和 i / x要注意剔除 x i 的情况。但在这个问题里因为 n 最大只有 1000直接枚举 1 到 i - 1 也不会超时。为了以后遇到大数据量也能应对我给出一个稍微优化过的版本class Solution: def divisorGame(self, n: int) - bool: dp [False] * (n 1) dp[1] False for i in range(2, n 1): # 枚举 i 的真因子 for x in range(1, int(i ** 0.5) 1): if i % x 0: # x 是因子且 x i if not dp[i - x]: dp[i] True break # i // x 也是因子需要满足 i // x i y i // x if y i and not dp[i - y]: dp[i] True break return dp[n]这个实现里有两个容易踩的坑一是 x 等于 i 的情况比如 i 1 时枚举到 x 1但 x 必须小于 i所以 dp[1] False 是直接初始化的循环也从 2 开始。二是 i // x 可能等于 i这只有在 x 1 时发生但代码里加了 y i 的判断来避免 dp[0] 这种越界或误判。其实对这道题来说枚举 1 到 i - 1 的写法更直白也不用担心上面那个“成对因子”的坑class Solution: def divisorGame(self, n: int) - bool: dp [False] * (n 1) for i in range(2, n 1): for x in range(1, i): if i % x 0 and not dp[i - x]: dp[i] True break return dp[n]这样写更符合直觉时间复杂度 O(n^2)。虽然题目的 n 最多只有 1000平方级没有任何压力但如果你把 n 放大到 10 万这就是另一个故事了。所以可以在面试时主动提一句如果要进一步优化也可以先用埃氏筛预处理每个数的因子把枚举成本摊薄不过在这个数据范围下没什么必要。动态规划的空间复杂度是 O(n)因为只开了一个长度为 n 1 的布尔数组。跑完 n 1000你可以顺手验证一下 dp 数组里所有偶数位都是 True、奇数位都是 False这就和数学规律对上了。3.3 为什么这道题用 DP 是“杀鸡用牛刀”如果只想通过 LeetCode 1025DP 确实有点绕远路但我不建议你跳过这个解法直接记奇偶结论。因为 LeetCode 上像“除数博弈”这样可以用数学规律秒杀的题目毕竟不多多数博弈题还是需要状态搜索、DP、记忆化递归这类通用手段。比如经典的“石子游戏”“预测赢家”以及各种变体拿到题目后你要能快速判断适合用哪种武器。另外一个原因是这道题很容易被出题人“加码”。比如把规则改成“每次只能选择 x 为 1 或某个固定质数”或者“n 减到 0 的人获胜”这种时候奇偶规律大概率会变一个 if 判断就失效了。但 DP 框架仍然能很好工作只是转移条件要相应调整。算法基础扎实的人面对这种改动会从容得多。4. 递归与记忆化搜索从“刷题直觉”到“代码落地”4.1 直接递归会超时吗很多人的第一反应是写一个递归函数模拟游戏当前数字为 n递归判断是否存在某个 x 能把对方送到必败态。这个思路和 DP 状态转移方程是同构的只是方向相反——一个是自顶向下一个是自底向上。朴素递归的代码大概长这样class Solution: def divisorGame(self, n: int) - bool: def can_win(num): if num 1: return False for x in range(1, num): if num % x 0 and not can_win(num - x): return True return False return can_win(n)这版代码在 n 1000 时测一下会明显卡顿因为它的时间复杂度是指数级的。原因是同一状态会被反复计算比如 n 8 时递归会去算 n 7、6、5、4 等大量重复状态。每个状态的子问题之间有大量重叠所以必须做记忆化。4.2 加一个缓存数组递归就稳了加缓存的方式很朴素用一个 memo 数组记录每个数字的计算结果初始化为 -1 表示未计算。遇到重复状态直接返回class Solution: def divisorGame(self, n: int) - bool: memo [-1] * (n 1) memo[1] 0 # False def can_win(num): if memo[num] ! -1: return memo[num] 1 for x in range(1, num): if num % x 0 and not can_win(num - x): memo[num] 1 return True memo[num] 0 return False return can_win(n)这个版本和 DP 本质上是同一个东西时间复杂度也是 O(n^2)空间复杂度 O(n)。不同之处只是遍历方向。实际使用中我更推荐在面试时先写记忆化递归因为它最容易向面试官解释思路“每到一个状态我尝试所有可能的走法只要有一条能把对手送到必败路线的路我就赢”——这就是一个很自然的递归逻辑。写完后如果面试官要求优化空间或者进一步分析你可以在白板上顺势推出 DP 版本显得思路有层次。4.3 两种解法放在一起看思维模型完全不同这里有个值得展开的点。递归和 DP 虽然算的是同一张表但背后的“思维模型”有差异递归是“向后看”——我从当前 n 出发设想每种 x 的选择会把我带到哪个状态再看那个状态对对手是不是必败。DP 是“向前推”——我从最小的状态开始逐步算出所有状态的胜负属性最后取 dp[n]。如果你的 n 很小哪个都无所谓。但如果你在做一道范围更大的变种题DP 的优势是可以通过打表找出周期或数学规律递归的优势则是状态转移复杂时不需要严格排序依赖只要递归能够终止就行。我个人的经验是遇到博弈类题目先用递归记忆化快速验证思路对不对然后看数据范围决定是否要转成 DP再看是否存在“必胜/必败状态交替出现”的结构性规律。这套流程用来刷题和面试应对都很稳。5. 实战视角面试考这道题时面试官到底想听什么5.1 很多人忽略了“为什么偶数一定赢”这个关键论证我听过不少候选人这样回答“我打表发现偶数就赢奇数就输所以返回 n % 2 0。”这个答案不能算错但它完全没有体现算法能力。面试官听到这个回答后大概率会追问一句“你能证明一下吗”这时候假如你只会背结论场面就会非常尴尬。反过来如果候选人能像前面 2.3 节那样先说明“奇数经过任何合法操作都会变成偶数而偶数一定可以通过选 x 1 变成奇数”然后再用数学归纳法收尾面试官基本就能确认你具备扎实的算法思维。这道题作为简单题出现在面试中目的往往不是考你会不会写循环而是看你能不能把一个博弈问题抽象成状态转换并且完成证明闭环。5.2 时间复杂度、空间复杂度的考察变化如果你写的是 DP 解法面试官一般会追问时间复杂度和空间复杂度以及能不能优化。这时候你要能流利说出 O(n^2) 的来源对每个 i 都要枚举它的因子因子枚举的规模均摊大约是 O(log n) 到 O(n)这里简化分析可以认为是 O(n)。因为 n 最大 1000所以 O(n^2) 完全没问题。有些面试官喜欢“如果你把 n 改成 10^9这道题还能用 DP 吗”这种问题。答案当然是不能再用 O(n) 空间的数组需要走数学推导直接判断奇偶性。这就是一个很自然的引导从 DP 的通用性过渡到数学规律的简洁性。另外还有个细节也值得留意在计算因子时如果写成 for x in range(1, num)大家都能理解如果对每个因子对同时处理比如 for x in range(1, int(sqrt(n)) 1)需要考虑 x 和 n // x 两者是否都是合法因子关系。这个细节反映出候选人对边界条件的敏感度。我面试时如果候选人能自己指出“排除 x 等于 n 的情况”我在这一项的评分就会明显提高。5.3 警惕“背题式”答案面试官会故意改条件刷题量大的朋友都对 1025 很熟悉面试官也知道你熟悉。所以现在不少面试官会现场改编一下比如把“选择 x 是 n 的因子”改成“选择 x 是 n 的质因子”或者“把 n 变成 n / x 而不是 n - x”看你能不能变通。我拿“改成质因子”举个例子。假设规则变成选择 n 的一个质因子 x把 n 变成 n - x其他条件不变。那原来的奇偶规律还成立吗把 n 6 拿出来试6 的质因子是 2 和 3Alice 选 2 得到 4选 3 得到 3。如果她选 3Bob 面对 33 只能变到 2Alice 再面对 2 时只能变到 1Bob 面对 1 输——这个推下来 Alice 依然是赢的。你观察一下就会发现质因子里可能有奇数也可能有偶数状态转移不再是简单的奇数必转偶数、偶数必能转奇数所以要重新推导。这种现场加码就是在考验你“有没有真正理解解题工具而不是背模板”。所以我的建议很明确做这道题时不管你能多快背出答案一定要把动态规划和数学归纳的推导过程亲手写一遍、推一遍。这样面试官无论怎么改你都能沿着基本原理走。5.4 现场口述答题的参考框架如果你准备在面试时讲这道题我推荐一个话术框架先描述状态当前数字 n 下当前玩家是否能赢记为 f(n)。找出递推关系f(n) 存在一个真因子 x使得 f(n-x) 为 false。说明终止条件f(1) false因为没有任何合法选择。展示常规解法记忆化搜索或动态规划。进一步推导数学规律证明奇偶结论给出 O(1) 解。这个过程讲下来面试官看到的是你会“先想后做”而不是“提交试错”。哪怕最后代码只写了一行前期分析已经展现出了足够的深度。6. 变种问题的延展思考这类题还能怎么考6.1 改变胜负条件、操作规则后的快速推演LeetCode 1025 本身是入门级的博弈题但它非常适合作为母体延展出各种变体。你可以拿几个改动方向来训练自己的思维每个方向都值得推一推找找新规律改动一把 n 变成 n / x。这种规则下游戏结束条件会完全不同因为数字会快速缩小因子的分布性质会左右胜负值得重新建立递推或找规律。改动二限制 x 只能是质数。像刚才说的状态转移不再和奇偶性一一对应。用 Python 快速打表后常常能看到周期性的胜负规律那就可以往“找周期”方向思考。改动三把“谁无法操作谁输”改成“谁先达到目标状态谁赢”。这是另一种博弈模型常用套路是从目标状态倒推前一步的必胜状态。改动四允许多个数字同时存在玩家每次选择其中一个数字操作。这属于“组合博弈”范畴理论上有 SG 函数这类工具可以处理不过这就远超简单题的难度了。当你觉得 1025 太简单时可以拿这些变种来练手。练的过程会帮你把“枚举因子 状态转移 / 数学归纳”这个技能组合彻底内化。6.2 同类型题目对照LeetCode 上的其他“数字博弈”LeetCode 里有一些题和 1025 属于近亲比如 292 Nim 游戏规则是每次可以拿 1 到 3 个石头谁拿最后一个谁赢。它的结论也极其优雅n 是 4 的倍数时先手输否则先手赢。和 1025 一样292 的常规解法也可以写 DP但最优解是一个简单的取模判断。还有 877 石子游戏、486 预测赢家、1140 石子游戏 II 等它们都是典型的博弈 DP。你会发现一个模式很多“纸面博弈”的题目只要两个人的角色完全对称、没有隐藏信息和随机因素就可以抽象成“当前局面是否必胜”的递推或数学规律。这也是我在 LeetCode 刷题时特别喜欢总结的一类题目做多了以后看到“Alice 和 Bob 轮流玩游戏”这种描述脑子里就会自动蹦出几个问题双方角色对称吗操作会让变量单调变化吗必胜状态有什么结构吗把这几个问题答完解题方向基本就定了。如果你准备系统刷这类题我建议用一张表把同类题目整理出来每道题都记录规则差异、状态定义、转移方程、最优解的时间复杂度。整理几题后你会发现“数字博弈”的一整套方法论变得有血有肉而不再是一道道孤立的题。6.3 从刷题到工程这类思维真正用在哪里可能有朋友会问这题这么数学化实际工程里用得上吗说实话真的很少会遇到“Alice 和 Bob 轮流选因子”这种场景。但博弈递推背后那套“当前决策要让对手陷入最差局面”的思维方式在很多系统设计里是能用上的。比如做一个回合制小游戏的 AI你需要对局面做极小化极大搜索这和 dp[i] 是否存在使对手必败的走法本质是完全一致的。再比如一些资源分配的对抗性算法或者棋类游戏里的胜负判断模块状态爆炸时还需要结合记忆化搜索剪枝这和 LeetCode 1025 的递归记忆化是一模一样的结构。理解了一个简单题里的核心逻辑后续迁移到这些工程场景时你会觉得底层代码顺理成章。还有个更贴近日常的例子产品里经常要做一个“胜负判定流程”如果规则复杂最稳妥的实现不是人工硬编码所有分支而是把这个“玩家选操作 - 状态更新 - 轮到对方”的循环抽象成一个纯函数用状态转移表或者记忆化搜索统一处理。这正好就是这道题里递归搜索的结构。所以别看题简单它背后是一整套对抗性游戏建模的雏形。7. 我做完这道题后留下的一些小习惯最后分享一个我个人的习惯。LeetCode 1025 这类“结论秒杀”的题目我做完之后不会立刻划走而是会把推导过程压缩成几行注释写进代码里。比如class Solution: def divisorGame(self, n: int) - bool: # 奇数必输奇数因子全为奇数奇数减奇数得偶数对手拿到偶数 # 偶数必赢选 x 1把奇数 n - 1 交给对手 return n % 2 0这两个注释看起来简单但它们记录的是整道题最核心的洞见。过一个月再回来看代码还在洞察不会丢。另一个习惯是做完题后在草稿纸上把 n 1 到 n 10 的胜负表列一遍。列完你就会发现数学结论不是靠背的而是通过一张小表格自然“长”出来的。这个方法对所有博弈类题目都适用尤其是以后遇到没有规律可循的困难博弈题打表找周期往往是最快打开思路的方式。我对这道题的整体评价是代码难度几乎为零思维含金量却不低。它很适合放在面试前热身也适合作为给初学者讲解“先证明再编码”理念的入门范例。如果你能把它背后的归纳证明和 DP 推导都消化干净那么它带给你的收获会比一百道无脑遍历的题目还要多。