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，满足：
  1. 0 < x < N
  2. N % 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。轮到鲍勃，N=1无法操作，鲍勃输，爱丽丝赢。True。
• N = 3：爱丽丝只能选择x = 1（3的因数只有1），黑板变为2。此时局面等同于N=2且轮到鲍勃先手。根据上一条，N=2时先手赢，所以鲍勃会赢，爱丽丝输。False。
• N = 4：爱丽丝可以选择x = 1或x = 2。
  • 如果选x=1，局面变为N=3鲍勃先手。N=3先手输，所以鲍勃输，爱丽丝赢。
  • 如果选x=2，局面变为N=2鲍勃先手。N=2先手赢，所以鲍勃赢，爱丽丝输。
  • 爱丽丝会选择让自己赢的操作（x=1）。所以N=4爱丽丝赢。True。

观察结果：N = 1(False), 2(True), 3(False), 4(True)。一个大胆的猜想：当N为偶数时，爱丽丝赢；当N为奇数时，爱丽丝输。

这就是本题最精妙的数学结论。在深入代码之前，我们必须先理解为什么。

2. 数学原理深度解析：奇偶性的博弈

为什么奇偶性决定了胜负？我们可以从两个角度来理解。

2.1 角度一：数学归纳法证明

我们定义win(N)表示初始数字为N时，先手玩家是否能赢。

1. 基础情况：
   • N = 1：先手输。win(1) = False。
   • N = 2：先手赢。win(2) = True。
2. 归纳假设：假设对于所有k < N，命题“若k为偶数则win(k)=True，若k为奇数则win(k)=False”成立。
3. 归纳步骤：考虑N。
   • 情况 A：N为奇数。N的因数x只能是奇数（因为奇数不可能被偶数整除）。所以x是奇数。 那么N - x= 奇数 - 奇数 =偶数。 根据归纳假设，面对一个偶数N-x，作为后手的玩家（即原局面的先手玩家）将处于必胜局面。因此，对于奇数N，先手玩家无论怎么走，都会留给对手一个必胜的偶数局面。所以win(N) = False。
   • 情况 B：N为偶数。N至少有一个因数是1。1是奇数。 那么N - 1= 偶数 - 奇数 =奇数。 根据归纳假设，面对一个奇数N-1，作为后手的玩家（即原局面的先手玩家）将处于必败局面。 因此，先手玩家可以选择x=1，主动将必败的奇数局面丢给对手。所以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又会变成偶数。如此循环，爱丽丝总能将奇数局面留给鲍勃。最终，必然是鲍勃面对N=1这个奇数而输掉。
• 如果初始N是奇数：那么爱丽丝的第一步操作后，N-x必然是偶数（奇数-奇数）。这就相当于将“先手优势”拱手让给了鲍勃。此后鲍勃作为偶数局面的先手，将复制上面爱丽丝的策略，最终必胜。

所以，胜负在游戏开始时就已经由N的奇偶性决定了。这解释了为什么双方“发挥最佳水平”的假设很重要——因为只要有一方懂得这个策略，他就掌握了必胜/必败的法门。

3. 从暴力递归到动态规划：编程思维的递进

虽然数学解法简洁，但掌握基于搜索的解法对于理解博弈问题和动态规划至关重要。我们一步步来。

3.1 环境准备与前置条件

我们将使用 Python 3 进行实现。不需要任何额外的第三方库。确保你的 Python 环境已就绪。你可以通过命令行输入python --version来检查。

3.2 解法一：暴力递归（自顶向下）

这是最直接的思路：模拟游戏进程。 定义一个递归函数can_win(n)，表示在当前数字n时，当前行动玩家是否能赢。

• 基准情况：n == 1时，当前玩家无法行动，输，返回False。
• 递归情况：遍历所有可能的x（n的因数，且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 (如 n>30) 会超时。 """ # 辅助递归函数 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(f"N=1: {sol.divisorGame(1)}") # 应输出 False print(f"N=2: {sol.divisorGame(2)}") # 应输出 True print(f"N=3: {sol.divisorGame(3)}") # 应输出 False # 注意：N=30 以上调用可能会非常慢

问题：这个解法存在大量的重复子问题计算。例如，计算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(f"N=1: {sol.divisorGame(1)}") # False print(f"N=2: {sol.divisorGame(2)}") # True print(f"N=3: {sol.divisorGame(3)}") # False print(f"N=4: {sol.divisorGame(4)}") # True print(f"N=10: {sol.divisorGame(10)}") # True print(f"N=99: {sol.divisorGame(99)}") # False (奇数)

优化点：

1. 缓存：memo列表避免了重复计算。
2. 因数遍历优化：因数成对出现，只需遍历到sqrt(n)，将时间复杂度从 O(N) 降低到 O(√N)。这是求因数时的常用技巧。

3.4 解法三：动态规划（自底向上）

记忆化搜索是“递归+缓存”，我们也可以使用迭代的方式，从最小的子问题 (n=1) 开始，逐步计算到n=N。这是标准的动态规划。

定义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(f"N={N}: {sol.divisorGame(N)}")

输出结果：

N=1: False N=2: True N=3: False N=4: True N=10: True N=99: False N=100: 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(f"Error at N={N}: DP={dp_result}, Math={math_result}") print("All tests passed (if no error above).") # 快速输出几个例子 print(f"N=1: {sol.divisorGame(1)}") print(f"N=2: {sol.divisorGame(2)}") print(f"N=999: {sol.divisorGame(999)}")

4. 运行结果与效果验证

运行上述任何一段测试代码，你都能得到正确的结果。对于数学解法，你可以用动态规划的结果进行交叉验证，如前一个代码块所示。

如何判断成功：

1. 对于输入N=1，输出必须是False。
2. 对于输入N=2，输出必须是True。
3. 对于更大的N，结果必须符合“偶数True，奇数False”的规律。

如果失败，第一步应该看哪里：

• 递归/DP解法失败：检查因数遍历的逻辑是否正确，特别是边界条件（x < n）和因数的成对处理。
• 数学解法失败：几乎不可能失败，除非你写错了n % 2 == 0。但请确保理解其证明，而不是死记结论。

5. 常见问题与排查思路

6. 最佳实践与工程建议

虽然本题的数学解法极其简单，但其中的思维过程和编程实践具有普遍意义。

1. 从暴力解法开始思考：面对一道新题，尤其是博弈类问题，先不要想奇技淫巧。从最朴素的模拟（递归搜索）开始，理清游戏规则和状态定义。这是解决问题的坚实基础。
2. 识别重复子问题：在实现暴力递归时，要有意识地问自己：can_win(10)和can_win(8)是不是被计算了多次？一旦发现重复计算，就要想到用缓存（记忆化）来优化。这是动态规划思想的萌芽。
3. 尝试寻找规律：在得出暴力解或DP解后，不要满足于AC。尝试打印出小规模N（比如1到20）的结果，观察规律。很多“简单”题目的背后，都藏着可以大幅优化时间/空间复杂度的数学规律。
4. 理解而非记忆：对于“偶数赢奇数输”这个结论，死记硬背在面试中很危险。面试官可能会追问“为什么？”。你必须能清晰阐述数学归纳法的证明过程，或者用“控制奇偶局面”的策略来解释。这体现了你的逻辑推理能力。
5. 代码实现的细节：
   • 因数遍历优化：在需要求一个数的所有因数时，牢记只需遍历到其平方根。这是基础算法常识，能显著提升性能。
   • DP数组定义清晰：明确dp[i]代表什么（在数字i时当前行动玩家的胜负），这直接影响状态转移方程的正确性。
   • 使用Python布尔类型：dp数组用bool类型（True/False）比用int（1/0）更符合语义。

7. 总结与后续学习方向

“除数博弈”这道题的价值，远不止于一行return n % 2 == 0的代码。它提供了一个完美的学习路径：

1. 问题建模：将游戏规则转化为函数can_win(n)。
2. 暴力搜索：用递归模拟所有可能，这是最直观的解法。
3. 优化识别：发现重复子问题，引入记忆化（自顶向下DP）。
4. 迭代优化：改为自底向上的动态规划，思路更清晰。
5. 数学洞察：通过观察和小规模验证，发现奇偶性规律，并用数学归纳法严格证明。
6. 最终简化：得到时间复杂度 O(1)，空间复杂度 O(1) 的最优解。

这个过程涵盖了算法学习中“逐步优化”和“寻找本质”的核心思想。

后续学习方向：

• 更多博弈问题：LeetCode 上有许多类似的博弈题，如292. Nim 游戏（也是奇偶性）、877. 石子游戏（区间DP）、464. 我能赢吗（状态压缩+记忆化）。尝试用本文的思维路径去解决它们。
• 动态规划专题：DP是面试重中之重。从经典问题（背包、最长子序列、编辑距离）开始，理解状态定义和转移方程的设计。
• 数学归纳法训练：在算法问题中，尤其是涉及整数性质和递归的问题，数学归纳法是强大的证明工具。有意识地在分析问题时使用它。

回到开头的问题：为什么这道“简单”题值得深究？因为它训练的不是写代码的熟练度，而是分析问题、寻找规律、优化解法的系统性思维能力。在面试中，面试官看着你从暴力解法一步步推导到最优解，远比直接背出答案更能体现你的潜力。

建议你将本文的几种解法代码保存下来，并尝试用同样的思路去攻克其他博弈问题。理解一道题的深度，往往比刷十道题的广度更有价值。