除数博弈：从动态规划到奇偶性数学规律的算法优化

这类题目最值得先看的不是解法本身，而是它背后的数学规律。很多人一看到“博弈”两个字，就想着去模拟整个游戏过程，用递归或者动态规划去穷举所有可能，这当然能解，但往往不是最优解，尤其是在面试的紧张环境下。除数博弈（LeetCode 1025题）就是一个典型例子，它表面上是一个游戏模拟题，实际上是一个可以用数学归纳法秒杀的找规律题。如果你正在准备算法面试，或者想提升自己快速识别问题本质的能力，这篇文章会带你从最直接的模拟思路开始，一步步推导出那个“看一眼就知道答案”的数学结论，并解释为什么这个结论成立。

我建议你先别急着看答案，花一分钟想想：如果给你一个数字n，你和对手轮流操作，每次选择一个能被n整除的x（0 < x < n），然后将n替换为n - x。无法操作者输。假设双方都绝对聪明，你先手，你能赢吗？

下面，我会按照实际解题和思考的顺序，拆解这个问题。

1. 先理解规则，别急着写代码：问题重述与关键点

拿到任何题目，第一步永远是准确理解题意，找出所有约束和隐含条件。对于除数博弈：

• 游戏状态：当前数字n。
• 操作规则：轮到的一方必须选择一个整数x，满足：
  1. 0 < x < n
  2. n % x == 0（x是n的除数，且不能是n本身）。
• 状态转移：执行操作后，数字变为n - x。
• 终止条件：如果轮到某人时，n == 1，那么他无法找到满足条件的x（因为0 < x < 1的整数不存在），所以他输掉游戏。
• 目标：假设你和对手都采取最优策略。给定初始数字n，你先手，返回true如果你能赢，否则返回false。

这里有几个关键点容易被忽略，但直接影响解题思路：

1. “最优策略”：意味着双方每一步都会选择让自己最终获胜的操作。在博弈论中，这通常引导我们使用动态规划或递归，从终局倒推。
2. 操作改变的是n，不是x。你选了一个除数x，n就变成n-x。这个新数字可能不再有之前那些除数。
3. n的范围：根据题目描述，1 <= n <= 1000。这个范围不大，意味着即使使用O(n^2)的算法也完全可行，这给了我们使用动态规划的信心。

所以，最直接的思路就是模拟这个博弈过程，计算所有可能的状态。我们先从这个“笨办法”开始，它虽然慢，但能保证正确，并且是理解更优解法的基础。

2. 从“暴力”到清晰：递归与动态规划解法

2.1 递归思路（带记忆化）

我们可以定义一个函数canWin(n)，表示在当前数字为n且轮到当前玩家操作时，当前玩家是否能赢。

• 基础情况：如果n == 1，当前玩家没得选，直接输，返回false。
• 递归过程：对于当前的n，遍历所有可能的x（n的除数，且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(maxsize=None) 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)

这个解法逻辑正确，对于n=1000也能在要求时间内通过。但它不是最高效的，因为它隐藏了一个更简单的规律。

2.2 动态规划（递推）思路

我们可以用动态规划自底向上地计算。定义dp[i]为：数字i时，先手玩家是否能赢。

• dp[1] = False（先手直接输）
• 对于i > 1，我们需要遍历i的所有除数j（1 <= 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的结果，你会发现一个有趣的规律：

n=1: False n=2: True n=3: False n=4: True n=5: False n=6: True n=7: False n=8: True ...

看起来，当n是偶数时，先手（Alice）赢；当n是奇数时，先手输。真的是这样吗？我们来验证一下n=9。根据 DP，dp[9]会是False吗？手动推一下：9的除数有1, 3。

• 如果 Alice 选1，n变为8，dp[8]=True（Bob 面对 8 是必胜的），对 Alice 不利。
• 如果 Alice 选3，n变为6，dp[6]=True（Bob 面对 6 是必胜的），也对 Alice 不利。 所以dp[9]确实是False。规律似乎成立。

3. 数学归纳与证明：为什么偶数必胜，奇数必败？

现在我们从数学上证明这个观察到的规律。这不仅能让你记住结论，更能锻炼你的数学归纳和博弈分析能力。

命题：对于除数博弈，初始数字为n，双方最优策略下，先手玩家获胜当且仅当n是偶数。

证明（使用数学归纳法）：

1. 基础情况：

   • n = 1：奇数，先手无法操作，输。命题成立。
   • n = 2：偶数，先手只能选择x=1，将n变为1。后手面对1必输。所以先手赢。命题成立。

2. 归纳假设：假设对于所有k < n，命题成立。即：k为偶数时先手赢，k为奇数时先手输。

3. 归纳步骤：考虑n。

   • 情况 A：n是奇数。 奇数n的所有除数x都是奇数（因为如果x是偶数且能整除奇数n，那么n/x会是分数，矛盾）。所以，对于任何合法的x，n - x= 奇数 - 奇数 = 偶数。 根据归纳假设，对手面对偶数n-x时是必胜的。因此，无论先手选择哪个x，都会将局面变成一个对手必胜的偶数局面。所以，当n是奇数时，先手必败。
   • 情况 B：n是偶数。 偶数n至少有一个除数x=1（它是奇数）。先手可以选择x=1，那么n变为n-1，这是一个奇数。 根据归纳假设，对手面对奇数n-1时是必败的。因此，先手可以通过选择x=1，强制将局面变成一个对手必败的奇数局面。所以，当n是偶数时，先手有必胜策略（至少选择x=1就是必胜策略）。

   由归纳法，命题对任意正整数n成立。

核心洞见：这个证明揭示了游戏的关键——奇偶性。最优策略下，先手玩家如果拿到偶数，可以通过一直选择x=1，保证自己每次留给对手的都是奇数。而对手面对奇数时，无论怎么选（只能选奇除数），都会还回来一个偶数。如此循环，最终先手会将n=2的局面留给对手，自己获胜。

所以，最终的代码简单到令人发指：

class Solution: def divisorGame(self, n: int) -> bool: return n % 2 == 0

4. 从解题到举一反三：博弈类题目的常见套路与排查点

除数博弈提供了一个很好的范式：许多博弈问题看起来复杂，但可能存在简单的“必胜态/必败态”规律。处理这类题目时，我一般的排查和思考顺序是这样的：

4.1 判断问题类型

首先问自己：这是否是一个“公平组合游戏”？通常特征包括：

• 两人轮流操作。
• 完全信息（没有隐藏部分）。
• 无随机因素。
• 操作集合只依赖于当前状态，不依赖于玩家。
• 无法操作者输（正常游戏规则）。 除数博弈完全符合。对于这类游戏，一个强大的工具是Sprague-Grundy 定理，但很多简单题目可以通过找规律或DP解决。

4.2 尝试小规模模拟与找规律

就像我们刚才做的那样，不要一上来就想复杂算法。用手算或写个简单的程序打印出n=1,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 常见踩坑点

1. 忽略“最优策略”假设：题目说双方都聪明，意味着你要找的是“无论对手怎么应对，我都有办法赢”的策略，而不是模拟一两条随机路径。
2. 递归/DP状态定义错误：dp[i]必须明确是“当前轮到行动的玩家”的胜负，还是“先手玩家”的胜负。本题中，dp[i]表示“数字为i时，当前轮到的玩家（不一定是原始先手）的胜负”。在实现时，我们是从先手角度调用，逻辑是一致的。
3. 遍历除数效率：在DP解法中，内层循环for j in range(1, i)效率是O(n)，判断i % j == 0整体是O(n^2)。对于n<=1000可以接受。如果n很大，可以优化为只遍历j到sqrt(i)，但本题不需要。
4. 误解题意操作：一定要看清操作是n = n - x还是n = n / x或者其他。一字之差，解法完全不同。

回到除数博弈，我们现在有了三种解法：1) 记忆化递归，2) 动态规划，3) 数学结论。在面试中，最理想的回答路径是：

1. 阐述理解：复述题目，确认规则。
2. 提出暴力/通用解法：“首先，我们可以用递归+记忆化或者动态规划来模拟所有可能。定义状态dp[i]...”
3. 观察并优化：“在实现DP或者计算小样例时，我发现结果似乎只和奇偶性有关。偶数先手赢，奇数先手输。”
4. 给出证明：“我们可以尝试证明一下：当n是奇数时，它的所有除数都是奇数，所以n-x是偶数，留给对手必胜态；当n是偶数时，我可以选择x=1，留给对手奇数，即必败态。因此结论成立。”
5. 写出最终代码：给出return n % 2 == 0。

这个思考过程，展示了你从暴力到优化、从现象到本质的完整能力链，远比直接背答案要强。

所以，下次遇到类似的博弈题目，比如LeetCode 292. Nim 游戏（n % 4 != 0先手胜），或者LeetCode 877. 石子游戏（先手必胜），你就可以用类似的思路去分析：先从小数据找规律，再尝试用DP验证，最后思考能否数学归纳。这才是刷题提升的真正意义——掌握一类问题的解法，而不是一道题。