这类题目最值得先看的不是解法本身而是它背后的数学规律。很多人一看到“博弈”两个字就想着去模拟整个游戏过程用递归或者动态规划去穷举所有可能这当然能解但往往不是最优解尤其是在面试的紧张环境下。除数博弈LeetCode 1025题就是一个典型例子它表面上是一个游戏模拟题实际上是一个可以用数学归纳法秒杀的找规律题。如果你正在准备算法面试或者想提升自己快速识别问题本质的能力这篇文章会带你从最直接的模拟思路开始一步步推导出那个“看一眼就知道答案”的数学结论并解释为什么这个结论成立。我建议你先别急着看答案花一分钟想想如果给你一个数字n你和对手轮流操作每次选择一个能被n整除的x0 x n然后将n替换为n - x。无法操作者输。假设双方都绝对聪明你先手你能赢吗下面我会按照实际解题和思考的顺序拆解这个问题。1. 先理解规则别急着写代码问题重述与关键点拿到任何题目第一步永远是准确理解题意找出所有约束和隐含条件。对于除数博弈游戏状态当前数字n。操作规则轮到的一方必须选择一个整数x满足0 x nn % x 0x是n的除数且不能是n本身。状态转移执行操作后数字变为n - x。终止条件如果轮到某人时n 1那么他无法找到满足条件的x因为0 x 1的整数不存在所以他输掉游戏。目标假设你和对手都采取最优策略。给定初始数字n你先手返回true如果你能赢否则返回false。这里有几个关键点容易被忽略但直接影响解题思路“最优策略”意味着双方每一步都会选择让自己最终获胜的操作。在博弈论中这通常引导我们使用动态规划或递归从终局倒推。操作改变的是n不是x。你选了一个除数xn就变成n-x。这个新数字可能不再有之前那些除数。n的范围根据题目描述1 n 1000。这个范围不大意味着即使使用O(n^2)的算法也完全可行这给了我们使用动态规划的信心。所以最直接的思路就是模拟这个博弈过程计算所有可能的状态。我们先从这个“笨办法”开始它虽然慢但能保证正确并且是理解更优解法的基础。2. 从“暴力”到清晰递归与动态规划解法2.1 递归思路带记忆化我们可以定义一个函数canWin(n)表示在当前数字为n且轮到当前玩家操作时当前玩家是否能赢。基础情况如果n 1当前玩家没得选直接输返回false。递归过程对于当前的n遍历所有可能的xn的除数且1 x n。如果存在某个x使得在对手面对n - x时他会输即canWin(n - x) false那么当前玩家选择这个x就能迫使对手进入必败状态因此当前玩家能赢返回true。如果遍历完所有x对手面对每一个n - x都能赢即canWin(n - x) true那么当前玩家无论怎么选都会让对手进入必胜状态所以当前玩家必输返回false。这就是一个典型的“极小化极大”思路。直接递归会有大量重复计算所以需要加上记忆化Memoization。from functools import lru_cache class Solution: def divisorGame(self, n: int) - bool: lru_cache(maxsizeNone) def canWin(current_n): # 当前玩家面对数字 current_n if current_n 1: return False # 没得选输 # 寻找所有可能的除数 for x in range(1, current_n): if current_n % x 0: # 如果存在一个选择能让对手面对必败局面则当前玩家赢 if not canWin(current_n - x): return True # 所有选择都会让对手赢则当前玩家输 return False return canWin(n)这个解法逻辑正确对于n1000也能在要求时间内通过。但它不是最高效的因为它隐藏了一个更简单的规律。2.2 动态规划递推思路我们可以用动态规划自底向上地计算。定义dp[i]为数字i时先手玩家是否能赢。dp[1] False先手直接输对于i 1我们需要遍历i的所有除数j1 j i且i % j 0。如果存在一个除数j使得dp[i - j] False即对手在i-j时必输那么先手玩家选择j就能赢所以dp[i] True。否则dp[i] False。class Solution: def divisorGame(self, n: int) - bool: if n 1: return False # dp[i] 表示数字为 i 时先手是否能赢 dp [False] * (n 1) dp[1] False # 基础情况 for i in range(2, n 1): # 检查 i 的所有除数 for j in range(1, i): if i % j 0: # 如果存在一个选择 j能让对手(dp[i-j])处于必败则当前先手赢 if not dp[i - j]: dp[i] True break # 找到一个必胜策略即可 return dp[n]运行这个 DP 解法并打印出前几个n的结果你会发现一个有趣的规律n1: False n2: True n3: False n4: True n5: False n6: True n7: False n8: True ...看起来当n是偶数时先手Alice赢当n是奇数时先手输。真的是这样吗我们来验证一下n9。根据 DPdp[9]会是False吗手动推一下9的除数有1, 3。如果 Alice 选1n变为8dp[8]TrueBob 面对 8 是必胜的对 Alice 不利。如果 Alice 选3n变为6dp[6]TrueBob 面对 6 是必胜的也对 Alice 不利。 所以dp[9]确实是False。规律似乎成立。3. 数学归纳与证明为什么偶数必胜奇数必败现在我们从数学上证明这个观察到的规律。这不仅能让你记住结论更能锻炼你的数学归纳和博弈分析能力。命题对于除数博弈初始数字为n双方最优策略下先手玩家获胜当且仅当n是偶数。证明使用数学归纳法基础情况n 1奇数先手无法操作输。命题成立。n 2偶数先手只能选择x1将n变为1。后手面对1必输。所以先手赢。命题成立。归纳假设假设对于所有k n命题成立。即k为偶数时先手赢k为奇数时先手输。归纳步骤考虑n。情况 An是奇数。 奇数n的所有除数x都是奇数因为如果x是偶数且能整除奇数n那么n/x会是分数矛盾。所以对于任何合法的xn - x 奇数 - 奇数 偶数。 根据归纳假设对手面对偶数n-x时是必胜的。因此无论先手选择哪个x都会将局面变成一个对手必胜的偶数局面。所以当n是奇数时先手必败。情况 Bn是偶数。 偶数n至少有一个除数x1它是奇数。先手可以选择x1那么n变为n-1这是一个奇数。 根据归纳假设对手面对奇数n-1时是必败的。因此先手可以通过选择x1强制将局面变成一个对手必败的奇数局面。所以当n是偶数时先手有必胜策略至少选择x1就是必胜策略。由归纳法命题对任意正整数n成立。核心洞见这个证明揭示了游戏的关键——奇偶性。最优策略下先手玩家如果拿到偶数可以通过一直选择x1保证自己每次留给对手的都是奇数。而对手面对奇数时无论怎么选只能选奇除数都会还回来一个偶数。如此循环最终先手会将n2的局面留给对手自己获胜。所以最终的代码简单到令人发指class Solution: def divisorGame(self, n: int) - bool: return n % 2 04. 从解题到举一反三博弈类题目的常见套路与排查点除数博弈提供了一个很好的范式许多博弈问题看起来复杂但可能存在简单的“必胜态/必败态”规律。处理这类题目时我一般的排查和思考顺序是这样的4.1 判断问题类型首先问自己这是否是一个“公平组合游戏”通常特征包括两人轮流操作。完全信息没有隐藏部分。无随机因素。操作集合只依赖于当前状态不依赖于玩家。无法操作者输正常游戏规则。 除数博弈完全符合。对于这类游戏一个强大的工具是Sprague-Grundy 定理但很多简单题目可以通过找规律或DP解决。4.2 尝试小规模模拟与找规律就像我们刚才做的那样不要一上来就想复杂算法。用手算或写个简单的程序打印出n1,2,3,4,5,6,7,8...的结果。观察规律结果是否呈现周期性例如本题的奇偶性是否和某个数学性质质数、平方数、斐波那契数相关必败态P-position和必胜态N-position是否有递推关系本题中所有偶数都是N-position所有奇数都是P-position。4.3 设计动态规划状态如果规律不明显DP是通用解法。关键是如何定义状态。状态通常就是游戏的当前局面如本题的n。状态转移从当前状态枚举所有合法操作到达下一个状态。如果存在一个操作能到达一个对手必败的状态那么当前状态是必胜的否则是必败的。初始化确定游戏结束的终局状态通常是无法操作的状态是必败的。 本题的dp[i]定义就是经典范例。4.4 优化与数学证明找到规律如偶数必胜后不要满足于“看起来对”。尝试用数学归纳法或反证法去证明它。证明过程能加深你对问题本质的理解。即使证明不严谨在面试中说出清晰的推理思路也比只背结论得分高得多。4.5 常见踩坑点忽略“最优策略”假设题目说双方都聪明意味着你要找的是“无论对手怎么应对我都有办法赢”的策略而不是模拟一两条随机路径。递归/DP状态定义错误dp[i]必须明确是“当前轮到行动的玩家”的胜负还是“先手玩家”的胜负。本题中dp[i]表示“数字为i时当前轮到的玩家不一定是原始先手的胜负”。在实现时我们是从先手角度调用逻辑是一致的。遍历除数效率在DP解法中内层循环for j in range(1, i)效率是O(n)判断i % j 0整体是O(n^2)。对于n1000可以接受。如果n很大可以优化为只遍历j到sqrt(i)但本题不需要。误解题意操作一定要看清操作是n n - x还是n n / x或者其他。一字之差解法完全不同。回到除数博弈我们现在有了三种解法1) 记忆化递归2) 动态规划3) 数学结论。在面试中最理想的回答路径是阐述理解复述题目确认规则。提出暴力/通用解法“首先我们可以用递归记忆化或者动态规划来模拟所有可能。定义状态dp[i]...”观察并优化“在实现DP或者计算小样例时我发现结果似乎只和奇偶性有关。偶数先手赢奇数先手输。”给出证明“我们可以尝试证明一下当n是奇数时它的所有除数都是奇数所以n-x是偶数留给对手必胜态当n是偶数时我可以选择x1留给对手奇数即必败态。因此结论成立。”写出最终代码给出return n % 2 0。这个思考过程展示了你从暴力到优化、从现象到本质的完整能力链远比直接背答案要强。所以下次遇到类似的博弈题目比如LeetCode 292. Nim 游戏n % 4 ! 0先手胜或者LeetCode 877. 石子游戏先手必胜你就可以用类似的思路去分析先从小数据找规律再尝试用DP验证最后思考能否数学归纳。这才是刷题提升的真正意义——掌握一类问题的解法而不是一道题。