LeetCode 1025 除数博弈：从动态规划到奇偶性数学解法的深度解析

如果你在 LeetCode 上刷到第 1025 题“除数博弈”第一反应是不是觉得这题有点“怪”题目描述很简单爱丽丝和鲍勃轮流玩游戏初始数字为N。轮到谁时谁就选择一个0 x N且N % x 0的数然后用N - x替换黑板上的数字N。如果轮到谁时无法再选择这样的x谁就输掉游戏。爱丽丝先手。问题是给定N如果爱丽丝能赢就返回True否则返回False。很多人的第一直觉是去模拟整个游戏过程尝试用递归或动态规划去穷举所有可能。这当然是一种解法但如果你真的这么做了可能会发现代码写起来有点绕而且对于大一点的N效率也不高。更关键的是你可能错过了这道题最核心的价值——它根本不是一道让你去模拟游戏的题而是一道披着游戏外衣的数学归纳法和奇偶性分析的经典例题。这道题在 LeetCode 上被标记为“简单”但它的“简单”恰恰体现在思维的转换上而不是代码的复杂度上。如果你只学会了模拟的解法那只是解决了这一道题但如果你理解了背后的数学原理你就掌握了一类“博弈游戏”问题的通用分析思路。这对于准备技术面试尤其是考察逻辑思维和数学归纳能力的面试至关重要。本文将带你彻底拆解“除数博弈”问题。我们不会满足于一种解法而是从最直观的暴力递归开始逐步优化到记忆化搜索和动态规划最后揭示那个“一行代码”就能解决的数学规律。更重要的是我们会深入探讨为什么这个规律成立以及如何培养自己从具体问题中抽象出数学模型的能力。无论你是正在刷题入门的新手还是想巩固动态规划和博弈论思想的进阶者这篇文章都将提供清晰的路径和可运行的代码。1. 问题重述与核心洞察这不是一道编程题而是一道数学题首先我们严格定义一下题目玩家爱丽丝Alice和鲍勃Bob爱丽丝先手。状态当前黑板上的数字N(N 1)。操作轮到当前玩家时必须选择一个整数x满足0 x NN % x 0即x是N的因数不包括N本身。状态转移选择x后黑板上的数字更新为N - x。终止条件如果轮到某个玩家时无法找到任何满足条件的x即N 1因为1没有小于它自身的正因数则该玩家输掉游戏。问题给定初始数字N假设双方都发挥最佳水平判断先手玩家爱丽丝是否能赢。关键洞察双方都“发挥最佳水平”意味着对于每一个状态N其结果先手赢或输是确定的。这引导我们思考是否存在一个只与N有关的属性直接决定了游戏的胜负如果你尝试手动模拟几个小例子规律很快就会浮现N 1爱丽丝无法操作直接输。False。N 2爱丽丝只能选择x 1因为2 % 1 0黑板变为1。轮到鲍勃N1无法操作鲍勃输爱丽丝赢。True。N 3爱丽丝只能选择x 13的因数只有1黑板变为2。此时局面等同于N2且轮到鲍勃先手。根据上一条N2时先手赢所以鲍勃会赢爱丽丝输。False。N 4爱丽丝可以选择x 1或x 2。如果选x1局面变为N3鲍勃先手。N3先手输所以鲍勃输爱丽丝赢。如果选x2局面变为N2鲍勃先手。N2先手赢所以鲍勃赢爱丽丝输。爱丽丝会选择让自己赢的操作x1。所以N4爱丽丝赢。True。观察结果N 1(False), 2(True), 3(False), 4(True)。一个大胆的猜想当N为偶数时爱丽丝赢当N为奇数时爱丽丝输。这就是本题最精妙的数学结论。在深入代码之前我们必须先理解为什么。2. 数学原理深度解析奇偶性的博弈为什么奇偶性决定了胜负我们可以从两个角度来理解。2.1 角度一数学归纳法证明我们定义win(N)表示初始数字为N时先手玩家是否能赢。基础情况N 1先手输。win(1) False。N 2先手赢。win(2) True。归纳假设假设对于所有k N命题“若k为偶数则win(k)True若k为奇数则win(k)False”成立。归纳步骤考虑N。情况 AN为奇数。N的因数x只能是奇数因为奇数不可能被偶数整除。所以x是奇数。 那么N - x 奇数 - 奇数 偶数。 根据归纳假设面对一个偶数N-x作为后手的玩家即原局面的先手玩家将处于必胜局面。因此对于奇数N先手玩家无论怎么走都会留给对手一个必胜的偶数局面。所以win(N) False。情况 BN为偶数。N至少有一个因数是1。1是奇数。 那么N - 1 偶数 - 奇数 奇数。 根据归纳假设面对一个奇数N-1作为后手的玩家即原局面的先手玩家将处于必败局面。 因此先手玩家可以选择x1主动将必败的奇数局面丢给对手。所以win(N) True。由此通过数学归纳法证明了我们的猜想。这个证明清晰地展示了博弈的核心先手玩家在偶数时总可以通过-1的操作将“必败”的奇数局面甩给对手。2.2 角度二游戏进程的必然性另一种理解方式是关注游戏终局。游戏何时结束当N变为1时轮到谁谁输。1是奇数。那么是谁将N变成了1这个奇数呢 由于每次操作N都减少N - N-x并且x至少为1所以N最终必然会降到1。如果初始N是偶数根据上面的归纳证明先手爱丽丝有能力控制局面使得每次轮到对手时N都是奇数。而奇数N的因数x只能是奇数所以N-x又会变成偶数。如此循环爱丽丝总能将奇数局面留给鲍勃。最终必然是鲍勃面对N1这个奇数而输掉。如果初始N是奇数那么爱丽丝的第一步操作后N-x必然是偶数奇数-奇数。这就相当于将“先手优势”拱手让给了鲍勃。此后鲍勃作为偶数局面的先手将复制上面爱丽丝的策略最终必胜。所以胜负在游戏开始时就已经由N的奇偶性决定了。这解释了为什么双方“发挥最佳水平”的假设很重要——因为只要有一方懂得这个策略他就掌握了必胜/必败的法门。3. 从暴力递归到动态规划编程思维的递进虽然数学解法简洁但掌握基于搜索的解法对于理解博弈问题和动态规划至关重要。我们一步步来。3.1 环境准备与前置条件我们将使用 Python 3 进行实现。不需要任何额外的第三方库。确保你的 Python 环境已就绪。你可以通过命令行输入python --version来检查。3.2 解法一暴力递归自顶向下这是最直接的思路模拟游戏进程。 定义一个递归函数can_win(n)表示在当前数字n时当前行动玩家是否能赢。基准情况n 1时当前玩家无法行动输返回False。递归情况遍历所有可能的xn的因数且1 x n。如果存在一个x使得can_win(n - x)返回False即对手在下一个局面必输那么当前玩家选择这个x就能赢返回True。如果所有x对应的can_win(n - x)都是True即无论怎么走对手都必胜那么当前玩家必输返回False。class Solution1: def divisorGame(self, n: int) - bool: 暴力递归解法。时间复杂度极高存在大量重复计算仅用于理解思路。 对于较大的 n (如 n30) 会超时。 # 辅助递归函数 def can_win(current_n): # 基准情况当前玩家无法操作输 if current_n 1: return False # 遍历所有可能的操作 x for x in range(1, current_n): if current_n % x 0: # x 必须是 current_n 的因数 # 如果存在一种操作能让对手在下一个局面必输则当前玩家赢 if not can_win(current_n - x): return True # 所有操作都无法让对手输则当前玩家输 return False return can_win(n) # 简单测试 if __name__ __main__: sol Solution1() print(fN1: {sol.divisorGame(1)}) # 应输出 False print(fN2: {sol.divisorGame(2)}) # 应输出 True print(fN3: {sol.divisorGame(3)}) # 应输出 False # 注意N30 以上调用可能会非常慢问题这个解法存在大量的重复子问题计算。例如计算can_win(10)时会计算can_win(9)、can_win(8)...而计算can_win(9)时又会重新计算can_win(8)。时间复杂度是指数级的。3.3 解法二记忆化搜索递归缓存为了优化暴力递归我们引入一个缓存字典或列表存储已经计算过的n对应的结果。这本质上是自顶向下的动态规划。class Solution2: def divisorGame(self, n: int) - bool: 记忆化搜索Memoization解法。 使用一个列表 memo 来存储子问题的解避免重复计算。 # memo[i] 表示数字为 i 时当前行动玩家是否能赢 # 初始化None 表示未计算 memo [None] * (n 1) # 基准情况 memo[1] False def can_win(current_n): # 如果已经计算过直接返回 if memo[current_n] is not None: return memo[current_n] # 遍历所有可能的因数 x # 优化因数总是成对出现的只需遍历到 sqrt(current_n) for x in range(1, int(current_n ** 0.5) 1): if current_n % x 0: # x 是一个因数 # 情况1选择 x (x ! current_n) if x current_n: if not can_win(current_n - x): memo[current_n] True return True # 情况2对应的另一个因数 current_n // x (如果它不等于 x 且小于 current_n) y current_n // x if y ! x and y current_n: if not can_win(current_n - y): memo[current_n] True return True # 所有操作都尝试过了无法让对手输 memo[current_n] False return False return can_win(n) # 测试 if __name__ __main__: sol Solution2() print(fN1: {sol.divisorGame(1)}) # False print(fN2: {sol.divisorGame(2)}) # True print(fN3: {sol.divisorGame(3)}) # False print(fN4: {sol.divisorGame(4)}) # True print(fN10: {sol.divisorGame(10)}) # True print(fN99: {sol.divisorGame(99)}) # False (奇数)优化点缓存memo列表避免了重复计算。因数遍历优化因数成对出现只需遍历到sqrt(n)将时间复杂度从 O(N) 降低到 O(√N)。这是求因数时的常用技巧。3.4 解法三动态规划自底向上记忆化搜索是“递归缓存”我们也可以使用迭代的方式从最小的子问题 (n1) 开始逐步计算到nN。这是标准的动态规划。定义dp[i]为当黑板数字为i时当前行动玩家即先手是否能赢。dp[1] False无法操作对于i 1我们遍历i的所有因数x。如果存在一个因数x使得dp[i - x] False即对手在i-x局面下必输那么当前玩家在i局面下就能赢即dp[i] True。否则dp[i] False。class Solution3: def divisorGame(self, n: int) - bool: 动态规划解法。自底向上填充 dp 数组。 if n 1: return False # dp[i] 表示数字为 i 时当前行动玩家是否能赢 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 是因数 # 情况1选择 x if x i and not dp[i - x]: dp[i] True break # 情况2选择另一个因数 i // x y i // x if y ! x and y i and not dp[i - y]: dp[i] True break # 如果已经找到必胜策略跳出内层循环 if dp[i]: break return dp[n] # 测试 if __name__ __main__: sol Solution3() test_cases [1, 2, 3, 4, 10, 99, 100] for N in test_cases: print(fN{N}: {sol.divisorGame(N)})输出结果N1: False N2: True N3: False N4: True N10: True N99: False N100: True动态规划解法的时间复杂度约为 O(N * √N)空间复杂度 O(N)。对于题目约束1 N 1000完全足够。3.5 解法四数学解法奇偶性基于第 2 部分的数学证明我们得到了最简洁、最高效的解法。class Solution4: def divisorGame(self, n: int) - bool: 数学解法。基于奇偶性分析。 时间复杂度 O(1)空间复杂度 O(1)。 return n % 2 0 # 测试 if __name__ __main__: sol Solution4() # 快速验证前100个数 for N in range(1, 101): dp_result Solution3().divisorGame(N) math_result sol.divisorGame(N) if dp_result ! math_result: print(fError at N{N}: DP{dp_result}, Math{math_result}) print(All tests passed (if no error above).) # 快速输出几个例子 print(fN1: {sol.divisorGame(1)}) print(fN2: {sol.divisorGame(2)}) print(fN999: {sol.divisorGame(999)})4. 运行结果与效果验证运行上述任何一段测试代码你都能得到正确的结果。对于数学解法你可以用动态规划的结果进行交叉验证如前一个代码块所示。如何判断成功对于输入N1输出必须是False。对于输入N2输出必须是True。对于更大的N结果必须符合“偶数True奇数False”的规律。如果失败第一步应该看哪里递归/DP解法失败检查因数遍历的逻辑是否正确特别是边界条件x n和因数的成对处理。数学解法失败几乎不可能失败除非你写错了n % 2 0。但请确保理解其证明而不是死记结论。5. 常见问题与排查思路问题现象可能原因排查方式解决方案暴力递归超时Time Limit ExceededN稍大如30时指数级复杂度导致计算时间爆炸。这是预期行为说明需要优化。必须使用记忆化搜索或动态规划来避免重复计算。动态规划结果错误对于某些N1.dp数组初始化错误。2. 因数遍历逻辑有误漏掉了某些因数。3. 状态转移条件写反not dp[i-x]是关键。1. 打印dp数组前几个值如dp[1]到dp[10]手动验证。2. 对于出错的N手动列出其所有因数模拟dp计算过程。1. 确认dp[1] False。2. 使用优化的因数遍历方法确保遍历到所有因数对(x, n//x)。3. 仔细检查if not dp[i - x]: dp[i] True的逻辑。记忆化搜索递归深度过大N很大时虽然本题限制1000但理论上Python递归可能有深度限制。Python默认递归深度约1000。对于N1000最坏情况递归深度可能接近1000可能触发RecursionError。1. 使用迭代的动态规划解法更安全。2. 可以使用sys.setrecursionlimit提高限制但非根本解决之道。不理解为什么数学解法成立对博弈过程和奇偶性分析理解不透彻。重新阅读第2部分并手动模拟N5,6,7,8的游戏过程用纸笔画出状态转移图。理解“偶数先手总可以通过-1将奇数局面给对手”这一核心策略。掌握数学归纳法的证明。6. 最佳实践与工程建议虽然本题的数学解法极其简单但其中的思维过程和编程实践具有普遍意义。从暴力解法开始思考面对一道新题尤其是博弈类问题先不要想奇技淫巧。从最朴素的模拟递归搜索开始理清游戏规则和状态定义。这是解决问题的坚实基础。识别重复子问题在实现暴力递归时要有意识地问自己can_win(10)和can_win(8)是不是被计算了多次一旦发现重复计算就要想到用缓存记忆化来优化。这是动态规划思想的萌芽。尝试寻找规律在得出暴力解或DP解后不要满足于AC。尝试打印出小规模N比如1到20的结果观察规律。很多“简单”题目的背后都藏着可以大幅优化时间/空间复杂度的数学规律。理解而非记忆对于“偶数赢奇数输”这个结论死记硬背在面试中很危险。面试官可能会追问“为什么”。你必须能清晰阐述数学归纳法的证明过程或者用“控制奇偶局面”的策略来解释。这体现了你的逻辑推理能力。代码实现的细节因数遍历优化在需要求一个数的所有因数时牢记只需遍历到其平方根。这是基础算法常识能显著提升性能。DP数组定义清晰明确dp[i]代表什么在数字i时当前行动玩家的胜负这直接影响状态转移方程的正确性。使用Python布尔类型dp数组用bool类型True/False比用int1/0更符合语义。7. 总结与后续学习方向“除数博弈”这道题的价值远不止于一行return n % 2 0的代码。它提供了一个完美的学习路径问题建模将游戏规则转化为函数can_win(n)。暴力搜索用递归模拟所有可能这是最直观的解法。优化识别发现重复子问题引入记忆化自顶向下DP。迭代优化改为自底向上的动态规划思路更清晰。数学洞察通过观察和小规模验证发现奇偶性规律并用数学归纳法严格证明。最终简化得到时间复杂度 O(1)空间复杂度 O(1) 的最优解。这个过程涵盖了算法学习中“逐步优化”和“寻找本质”的核心思想。后续学习方向更多博弈问题LeetCode 上有许多类似的博弈题如292. Nim 游戏也是奇偶性、877. 石子游戏区间DP、464. 我能赢吗状态压缩记忆化。尝试用本文的思维路径去解决它们。动态规划专题DP是面试重中之重。从经典问题背包、最长子序列、编辑距离开始理解状态定义和转移方程的设计。数学归纳法训练在算法问题中尤其是涉及整数性质和递归的问题数学归纳法是强大的证明工具。有意识地在分析问题时使用它。回到开头的问题为什么这道“简单”题值得深究因为它训练的不是写代码的熟练度而是分析问题、寻找规律、优化解法的系统性思维能力。在面试中面试官看着你从暴力解法一步步推导到最优解远比直接背出答案更能体现你的潜力。建议你将本文的几种解法代码保存下来并尝试用同样的思路去攻克其他博弈问题。理解一道题的深度往往比刷十道题的广度更有价值。