如果你在 LeetCode 上刷题时看到“除数博弈”这道题第一反应是不是觉得它像一道复杂的博弈论题目需要用到动态规划甚至更高级的算法很多同学会立刻开始构思状态转移方程试图用复杂的逻辑去模拟每一步的选择。然而这道题LeetCode 1025的真正解法可能会让你大跌眼镜——它本质上是一道披着博弈外衣的数学题核心逻辑简单到只需要一行代码就能判断胜负。这篇文章要解决的正是这种“认知偏差”带来的效率浪费。在算法面试和日常刷题中我们常常会不自觉地陷入“过度设计”的陷阱用复杂的思路去解决简单的问题这不仅浪费时间还可能因为代码冗长而引入更多错误。本文将带你彻底拆解“除数博弈”这道题揭示其背后的数学本质并提供从暴力递归、记忆化搜索到最终数学归纳的完整思考路径。更重要的是我们会探讨如何培养这种“识别问题本质”的算法直觉让你在遇到类似题目时能快速找到最高效的解法。读完本文你将不仅掌握这道题的所有解法更能获得一种更高级的刷题策略如何快速判断一道题的核心考点从而选择最优雅的解决方案。这对于备战技术面试、提升算法思维至关重要。1. 这道题真正在考什么博弈表象下的数学规律LeetCode 1025 “除数博弈”的题目描述如下爱丽丝和鲍勃一起玩游戏他们轮流行动。爱丽丝先手。 最初黑板上有一个数字N。在每个玩家的回合玩家需要执行以下操作选出任一x满足0 x N且N % x 0。用N - x替换黑板上的数字N。 如果玩家无法执行这些操作就会输掉游戏。 只有在爱丽丝在游戏中取得胜利时才返回True否则返回False。假设两个玩家都以最佳状态参与游戏。初看之下这是一个典型的“回合制”、“双方最优”、“状态转移”的博弈问题。很自然地我们会想到用动态规划DP来求解dp[i]表示当黑板数字为i时当前回合的玩家是否能获胜。然后我们尝试所有可能的x看是否存在一个选择使得对手进入必败状态。这个思路完全正确也是解决大多数博弈问题的通用方法。但“除数博弈”的特殊性在于它的输入N有一个隐藏的数学性质。我们通过暴力枚举和观察可以快速发现一个惊人的规律当N 1先手无法操作直接输。False当N 2先手只能选择x 1黑板变为1后手无法操作先手赢。True当N 3先手只能选择x 1黑板变为2。此时后手面对N2必胜态所以先手输。False当N 4先手可以选择x 1或x 2。选x1黑板变3后手面对3必败态所以先手赢。选x2黑板变2后手面对2必胜态先手输。由于双方都最优先手会选择能赢的x1。所以True。列出更多N1: FalseN2: TrueN3: FalseN4: TrueN5: FalseN6: True...规律浮出水面当N为偶数时先手爱丽丝必胜当N为奇数时先手必败。这才是本题真正的核心考点。面试官出这道题很可能不是想考察你写出一个完美的 DP而是希望你具备观察、归纳和证明简单规律的能力。在时间有限的面试中能快速发现并证明这个规律远比写出一段 DP 代码更能体现你的思维敏捷度。2. 核心概念博弈论、必胜态与必败态在深入解法之前我们需要明确几个关键概念这有助于理解所有解法的底层逻辑。1. 博弈论Game Theory与公平组合游戏本题属于“公平组合游戏”的简化模型。其特点是两个玩家轮流行动。游戏状态完全公开无隐藏信息。每一步的合法操作只取决于当前状态与玩家无关。无法操作者判负。 这类游戏通常可以用“必胜态”和“必败态”来分析。2. 必胜态N-position与必败态P-position必败态在当前状态下无论当前玩家如何操作对手都能获胜。也称为“先手必败态”。必胜态在当前状态下存在至少一种操作能使游戏进入一个“必败态”从而将失败抛给对手。也称为“先手必胜态”。3. 状态转移与递归关系对于本题我们可以定义win(N)表示当前黑板数字为N时当前回合的玩家是否能赢。基础情况N 1时无法操作当前玩家输win(1) False。状态转移对于N 1当前玩家可以遍历所有满足条件的x0 x N且N % x 0。如果存在某个x使得win(N - x) False即对手进入必败态那么当前玩家就能赢即win(N) True。否则win(N) False。用公式表示就是win(N) not all(win(N - x) for x in valid_x(N))或者win(N) any(not win(N - x) for x in valid_x(N))理解了这个递归关系我们就掌握了解决此类博弈问题的通用钥匙。接下来我们将从最直观的暴力递归开始逐步优化最终抵达那个简洁的数学结论。3. 环境准备与前置条件在开始编码前你需要一个可以运行 Python 的环境。本文的所有代码示例均基于 Python 3.6。基础环境操作系统Windows 10/11, macOS, 或 Linux 发行版如 Ubuntu均可。Python 版本建议使用 Python 3.8 或更高版本。你可以通过命令行输入python --version或python3 --version来检查。代码编辑器或 IDE任选其一即可。轻量级VS Code推荐安装 Python 扩展、Sublime Text、PyCharm Community Edition。在线环境如果你不想配置本地环境可以使用 LeetCode 的在线编辑器或 Google Colab。依赖库这道题的核心逻辑不依赖任何第三方库使用 Python 标准库即可。但在后续我们为了验证规律可能会用到matplotlib进行可视化这属于可选拓展。验证环境是否就绪打开你的终端Windows 上是 CMD 或 PowerShellmacOS/Linux 上是 Terminal创建一个测试文件。# 1. 创建一个工作目录并进入 mkdir leetcode_divisor_game cd leetcode_divisor_game # 2. 创建一个Python文件 touch divisor_game.py # Windows 系统可以使用type nul divisor_game.py 或直接右键新建。 # 3. 用编辑器打开该文件准备开始编码。4. 解法一暴力递归理解思路但不可行我们先从最符合直觉的暴力递归开始。这能帮助我们彻底理解游戏规则和状态转移但会因超时而无法通过所有测试用例。思路直接模拟游戏过程。函数can_win(N)判断当前数字N时当前行动的玩家是否能赢。def divisorGame_bruteforce(N: int) - bool: 暴力递归解法。 判断当前数字为N时当前行动的玩家是否能获胜。 # 基础情况N为1时无法操作当前玩家输 if N 1: return False # 遍历所有可能的x (0 x N 且 N % x 0) for x in range(1, N): if N % x 0: # 如果存在一个x使得对手在 N-x 的情况下不能赢则当前玩家能赢 if not divisorGame_bruteforce(N - x): return True # 如果所有可能的x都导致对手能赢则当前玩家输 return False # 测试一下小数字 if __name__ __main__: for i in range(1, 11): result divisorGame_bruteforce(i) print(fN {i}: {Alice wins if result else Bob wins})运行结果与问题N 1: Bob wins N 2: Alice wins N 3: Bob wins N 4: Alice wins N 5: Bob wins N 6: Alice wins ...对于小的N这个函数能正确工作。但它的时间复杂度是指数级的。对于每个N它需要遍历最多N-1个数并对每个有效的x递归调用自身。计算N30可能就需要很长时间绝对无法通过 LeetCode 的时间限制。关键教训暴力递归清晰地揭示了逻辑但缺乏效率。它帮助我们验证了前文提到的“必胜态/必败态”分析框架。接下来我们需要引入“记忆化”来优化。5. 解法二记忆化搜索自顶向下的动态规划记忆化搜索是优化递归的经典技术。我们用一个缓存字典或列表来存储已经计算过的win(N)的结果避免重复计算。思路定义一个缓存memomemo[N]存储数字N对应的胜负结果。递归函数计算win(N)时先查缓存命中则直接返回。未命中则进行计算并将结果存入缓存后再返回。def divisorGame_memoization(N: int) - bool: 记忆化搜索自顶向下DP解法。 from functools import lru_cache # 使用Python的lru_cache装饰器自动实现记忆化非常简洁 lru_cache(maxsizeNone) def can_win(n: int) - bool: # 基础情况 if n 1: return False # 遍历所有可能的除数 for x in range(1, n): if n % x 0: # 如果存在一个选择能让对手进入必败态则当前玩家必胜 if not can_win(n - x): return True # 所有选择都会让对手进入必胜态则当前玩家必败 return False return can_win(N) # 测试与性能对比 if __name__ __main__: import time test_n 1000 # 测试一个较大的数 start time.time() result_memo divisorGame_memoization(test_n) time_memo time.time() - start print(f记忆化搜索: N{test_n}, Result{result_memo}, Time{time_memo:.6f}s) # 尝试用暴力递归注释掉因为会极慢甚至递归深度爆炸 # start time.time() # result_brute divisorGame_bruteforce(test_n) # 不要轻易运行 # time_brute time.time() - start # print(f暴力递归: N{test_n}, Result{result_brute}, Time{time_brute:.6f}s)代码解释lru_cache(maxsizeNone)是 Python 标准库functools提供的装饰器它能自动为函数添加缓存功能存储所有不同参数调用时的返回值。这是实现记忆化最优雅的方式。递归逻辑与暴力版本一致但因为有了缓存每个n的状态只会被计算一次。时间复杂度优化到了大约 O(N²)因为对于每个n需要遍历最多n-1个可能的x。对于N1000也能在瞬间完成。这是 LeetCode 上能通过的常规解法之一。它体现了动态规划的思想并且代码清晰。然而我们还能更进一步。6. 解法三动态规划自底向上的递推自底向上的动态规划通常比记忆化搜索有更直观的迭代过程和更好的空间控制尽管本题差异不大。我们用一个数组dp来存储结果。思路dp[i]表示当黑板数字为i时当前行动的玩家是否能赢。初始化dp[1] False。从i 2递推到N对于每个i遍历所有可能的x0 x i且i % x 0。如果存在一个x使得dp[i - x] False那么dp[i] True因为当前玩家可以通过选择这个x让对手进入必败态。否则dp[i] False。def divisorGame_dp(N: int) - bool: 动态规划自底向上解法。 if N 1: return False # dp[i] 表示数字为i时当前玩家是否能赢 dp [False] * (N 1) # 创建长度为N1的数组索引0无用 dp[1] False # 基础情况 for i in range(2, N 1): # 遍历所有可能的除数x for x in range(1, i): if i % x 0: # 如果存在一个x能让对手进入必败态(dp[i-x]False)则当前玩家必胜 if not dp[i - x]: dp[i] True break # 找到一个必胜策略即可跳出循环 # 如果循环结束都没有找到必胜策略dp[i]保持为False初始化值 # 也可以显式设置else: dp[i] False return dp[N] # 测试与验证 if __name__ __main__: # 验证DP解法的正确性并与记忆化搜索对比 for n in range(1, 21): dp_result divisorGame_dp(n) memo_result divisorGame_memoization(n) print(fN{n:2d}: DP{dp_result}, Memo{memo_result}, Same{dp_result memo_result})运行结果N 1: DPFalse, MemoFalse, SameTrue N 2: DPTrue, MemoTrue, SameTrue N 3: DPFalse, MemoFalse, SameTrue ... N20: DPTrue, MemoTrue, SameTrue两种方法结果完全一致验证了正确性。复杂度分析时间复杂度O(N²)。外层循环 O(N)内层循环平均 O(N/2)。空间复杂度O(N)用于存储dp数组。这个解法已经足够好能通过 LeetCode 评测。但当我们打印出dp数组时那个隐藏的规律又出现了。def print_dp_pattern(up_to: int): dp [False] * (up_to 1) dp[1] False for i in range(2, up_to 1): for x in range(1, i): if i % x 0 and not dp[i - x]: dp[i] True break print(N : DP Result) for i in range(1, up_to 1): print(f{i:2d} : {dp[i]}) print(\nPattern (Even/Odd):) for i in range(1, up_to 1): expected (i % 2 0) # 偶数True奇数False print(fN{i:2d}: DP{dp[i]}, Expected(Even-True){expected}, Match{dp[i]expected}) if __name__ __main__: print_dp_pattern(20)输出会清晰地显示dp[i]为True当且仅当i为偶数。7. 解法四数学归纳与一行代码解现在我们来直面那个终极规律当 N 为偶数时先手爱丽丝必胜当 N 为奇数时先手必败。如何理解并证明这个规律我们可以从两个角度来思考角度一奇偶性分析游戏规则选出xx是N的正因子且x N然后用N - x替换N。关键观察如果N是奇数那么它的所有因子除了1都是奇数。奇数减奇数等于偶数。因此先手如果面对奇数N无论他选择哪个因子xx为奇数操作后黑板上的数字N - x都会变成偶数。对手后手将面对一个偶数。如果N是偶数呢偶数至少有一个因子是 1奇数。先手可以选择x 1这是一个合法的因子因为N % 1 0。操作后N - 1变成了奇数。对手将面对一个奇数。归纳推理已知N1奇数时先手必败。假设对于所有小于k的数规律成立偶数胜奇数败。考虑Nk若k是偶数先手可以通过选择x1将奇数k-1留给对手。根据假设对手面对奇数必败。所以先手必胜。若k是奇数先手必须选择一个奇数因子x因为奇数的因子都是奇数将偶数k-x留给对手。根据假设对手面对偶数必胜。所以先手必败。因此规律对任意N成立。角度二从DP结果反推我们之前用 DP 计算了前若干项发现结果完全由奇偶性决定。这本身就是一个强有力的经验证据。在面试中如果你能快速通过枚举前几个例子发现这个规律并给出上述奇偶性分析的证明就足以说服面试官。最终代码简洁到极致def divisorGame_math(N: int) - bool: 数学解法N为偶数时先手必胜为奇数时先手必败。 return N % 2 0 # 测试 if __name__ __main__: for n in [1, 2, 3, 4, 5, 10, 99, 100]: print(fN {n:3d}: Alice wins? {divisorGame_math(n)})复杂度时间复杂度O(1)。只进行了一次取模运算。空间复杂度O(1)。没有使用额外空间。这无疑是最高效、最优雅的解法。在 LeetCode 上提交时间和空间消耗都能击败接近100%的提交。8. 运行结果与效果验证现在让我们编写一个完整的测试脚本来验证所有解法的正确性和效率。import time def test_all_methods(up_to: int 20): 测试并比较所有解法在小范围内的正确性。 print( * 50) print(f测试 N 从 1 到 {up_to}) print( * 50) results {} methods [ (暴力递归, divisorGame_bruteforce), (记忆化搜索, divisorGame_memoization), (动态规划, divisorGame_dp), (数学解法, divisorGame_math) ] # 由于暴力递归太慢只测试到10 test_limit_for_brute min(up_to, 10) for name, func in methods: print(f\n--- {name} ---) start time.time() results[name] [] limit test_limit_for_brute if 暴力 in name else up_to for n in range(1, limit 1): try: res func(n) results[name].append(res) print(f N{n:2d}: {res}, end | if n % 5 0 else ) except RecursionError: print(f\n [递归深度超出停止测试]) break elapsed time.time() - start print(f\n 耗时: {elapsed:.6f} 秒) # 验证一致性 print(\n * 50) print(一致性检查 (对比数学解法):) print( * 50) reference results[数学解法] for name, res_list in results.items(): if name 数学解法: continue # 只对比有结果的部分 min_len min(len(reference), len(res_list)) if reference[:min_len] res_list[:min_len]: print(f {name:10s} ✓ 与数学解法结果一致) else: print(f {name:10s} ✗ 结果不一致) for i in range(min_len): if reference[i] ! res_list[i]: print(f 首个不一致点 N{i1}: {name}{res_list[i]}, 数学{reference[i]}) def benchmark_large_n(): 对大规模N进行性能基准测试排除暴力递归。 print(\n * 50) print(大规模 N 性能基准测试 (N1000)) print( * 50) test_n 1000 methods [ (记忆化搜索, divisorGame_memoization), (动态规划, divisorGame_dp), (数学解法, divisorGame_math) ] for name, func in methods: start time.time() result func(test_n) elapsed time.time() - start print(f{name:10s}: 结果{result}, 耗时{elapsed:.8f}秒) if __name__ __main__: # 定义之前的所有函数 (divisorGame_bruteforce, divisorGame_memoization, divisorGame_dp, divisorGame_math) # 这里需要把前面章节的四个函数定义复制过来或者导入 # 为了示例清晰假设它们都已定义在当前文件 test_all_methods(up_to15) benchmark_large_n()预期输出对于 N1 到 15所有方法除了暴力递归可能因深度问题提前终止的结果应该完全一致并且符合奇偶性规律。在性能测试中“数学解法”的耗时将是微秒甚至纳秒级而“记忆化搜索”和“动态规划”会有明显的耗时毫秒级但仍在可接受范围。这个验证过程不仅确认了解法的正确性也直观展示了不同算法在效率上的天壤之别。9. 常见问题与排查思路在理解和实现这道题时你可能会遇到以下问题问题现象可能原因排查方式解决方案暴力递归超时或递归深度错误N 稍大如20导致递归树爆炸超出 Python 默认递归深度约1000。观察问题出现的 N 值。使用sys.setrecursionlimit提高限制只能延缓无法解决指数级复杂度。放弃暴力递归。直接使用记忆化搜索或动态规划。记忆化搜索函数报错“unhashable type: list”使用了可变对象如列表作为lru_cache装饰函数的参数。检查被装饰函数的参数。lru_cache要求所有参数必须是可哈希的。确保参数是整数、字符串、元组等不可变类型。本题参数n是整数所以没问题。动态规划解法结果错误例如 N2 返回 False1.dp数组初始化错误。2. 内层循环条件或状态转移逻辑写错。3. 忽略了x必须是因子的条件 (N % x 0)。打印出小规模 N如1-5的dp数组中间值与手动推导结果对比。仔细检查代码1.dp[1] False。2. 内层循环for x in range(1, i):。3. 状态转移条件if i % x 0 and not dp[i - x]:。数学解法被质疑“怎么想到的”面试中直接给出return N % 2 0可能显得突兀缺乏推导过程。回顾解题步骤先尝试 DP观察前几项结果发现规律再用奇偶性证明。在面试中务必展示思考过程。可以先说“这道题可以用 DP 解”然后快速写出 DP 思路接着指出“但我发现一个规律……”最后给出数学解并证明。这体现了你的探索和归纳能力。不理解“双方都以最佳状态参与游戏”的含义误以为玩家会犯错或者需要模拟复杂的心理博弈。重新理解“最优博弈”假设每个玩家在任何局面下都会选择对自己最有利、对对手最不利的操作。在算法上这简化了问题。我们只需要计算在“绝对理性”下每个状态的胜负是确定的。状态dp[i]表示的就是在这种假设下当前玩家的胜负。10. 最佳实践与工程建议虽然这道题很简单但其中蕴含的思维模式和编码实践对刷题和面试极具价值。1. 刷题思维模式从通用到特化第一步理解问题并暴力模拟。无论题目多简单先写出最直观的解法如暴力递归确保完全理解游戏规则和状态定义。这是思维的锚点。第二步优化与泛化。分析暴力解法的瓶颈重复计算引入记忆化或 DP 进行优化。这是解决一大类问题的通用技能。第三步观察与归纳。在得到一系列正确结果如 DP 表后不要急于提交。停下来观察输出寻找模式。许多 LeetCode 题目都有隐藏的数学规律如本题的奇偶性、斐波那契数列、幂次关系等。第四步证明与简化。一旦发现规律尝试用数学归纳法或逻辑推理证明它。如果证明成立就能得到最简洁高效的解法。这往往是面试中的加分项。2. 代码实现建议清晰命名函数名如divisorGame_dp变量名如can_win,memo,dp让代码自解释。善用语言特性Python 的lru_cache可以极简地实现记忆化any()和all()函数可以让逻辑更清晰。添加注释对于关键的状态转移和边界条件添加简短注释方便自己回顾和他人阅读。编写测试像本文一样对小的输入进行验证确保基础情况正确。这能避免很多低级错误。3. 面试回答策略如果面试中遇到此题建议按以下步骤回答复述问题“这是一个两个玩家轮流操作、无法操作者输的公平博弈问题。”提出通用解法“对于这类问题通常可以用动态规划来解决。定义dp[i]表示当前数字为i时当前行动玩家的胜负。状态转移是...”展示优化/发现“但在实现 DP 或枚举小例子后我发现结果似乎只和N的奇偶性有关。偶数先手赢奇数先手输。”给出证明“我们可以这样证明当N为偶数时先手总可以选1将奇数留给对手当N为奇数时其因子都是奇数操作后必得偶数留给对手。结合基础情况N1奇数必败由数学归纳法可知规律成立。”给出最终代码“所以最简洁的解法是return N % 2 0。” 这种回答既展示了扎实的算法基础DP又体现了敏锐的观察力和数学思维。4. 关联题目与拓展学习理解“除数博弈”后你可以尝试以下 LeetCode 博弈题目巩固这类问题的解法292. Nim 游戏另一道经典的、有数学规律的简单博弈题。877. 石子游戏情况更复杂但依然可以用 DP 解决。486. 预测赢家更通用的博弈 DP 问题涉及数组和区间。1025. 除数博弈就是本题。 解决这些题目你会对“必胜态/必败态”分析和状态转移有更深的理解。从一道看似简单的题目出发我们遍历了从暴力递归、记忆化搜索、动态规划到最终数学归纳的完整解题链条。这道题的价值远不止于一个“return N % 2 0”的答案而在于它完美诠释了算法学习中的一种高阶思维在掌握通用解法的基础上主动寻找并证明更优的特化解法。在日常刷题和面试准备中养成“先实现再优化先枚举再归纳”的习惯。这不仅能帮你更快地解决具体问题更能训练你发现模式、抽象本质的能力这才是算法思维的核心。建议将本文的代码和思路收藏作为解决同类博弈问题的参考模板。下次遇到类似题目不妨先试试 DP再看看有没有隐藏的数学捷径。