最近在整理算法笔记时翻到了力扣第1025题“除数博弈”。这道题乍一看是个游戏规则简单但很多朋友第一次做的时候要么是硬着头皮去模拟游戏过程要么是尝试找规律但心里没底。题目描述是爱丽丝和鲍勃轮流玩游戏初始时有一个数字N。轮到谁时谁就选择一个x满足0 x N且N % x 0然后用N - x替换黑板上的数字N。如果轮到某个玩家时无法进行任何操作则判该玩家输。游戏规则清晰但直接去模拟每一步的选择对于稍大的N来说状态空间会非常复杂。这其实是一个典型的“博弈论”问题更具体地说是“公平组合游戏”中的一种。这类问题往往有一个共同点最终的胜负在游戏开始时就已经由初始状态决定了与玩家的具体操作无关。理解这一点是解决这类问题的关键。很多人会陷入一个误区认为必须去穷举所有可能的游戏路径才能判断胜负。但实际上对于“除数博弈”这类游戏我们真正需要关注的不是“怎么走”而是“当前状态是必胜态还是必败态”。一旦掌握了这个核心问题就会从一个复杂的模拟游戏简化成一个清晰的数学或动态规划问题。1. 先别急着写代码理解“必胜态”与“必败态”在公平组合游戏中双方操作规则相同且没有随机因素任何一个状态都可以被定义为“必胜态”或“必败态”。必胜态 (N-position)当前玩家有办法通过一次操作将游戏状态转移到一个“必败态”留给对手。必败态 (P-position)当前玩家所有可能的操作都会将游戏状态转移到一个“必胜态”留给对手。游戏的终止状态即无法操作的状态是必败态。因为轮到你了你却无路可走你输了。对于“除数博弈”当N 1时没有满足0 x 1的整数x当前玩家无法操作所以N1是必败态。我们的目标是判断N初始为某个数时先手玩家爱丽丝是否处于必胜态。那么如何判断一个N是必胜态还是必败态呢推理过程如下如果当前N是必败态那么爱丽丝先手就输了。如果当前N是必胜态那么爱丽丝就赢了。判断N的状态需要看是否存在一个xN的正因子且不等于N使得N - x这个新状态是必败态。如果存在这样的x那么爱丽丝就可以选择这个x把必败态扔给鲍勃自己稳操胜券。此时N是必胜态。如果所有可能的x对应的N - x都是必胜态那么无论爱丽丝怎么选都会把必胜态留给鲍勃自己就输了。此时N是必败态。这个过程天然形成了一个递归或动态规划的求解思路。我们可以从小到大地推导出每个N的状态。2. 从暴力递归到动态规划理清状态转移最直观的想法是写一个递归函数canWin(N)判断当前数字N是否必胜。def canWin(N): # 基础情况N1时无法操作必败 if N 1: return False # 遍历所有可能的操作x for x in range(1, N): if N % x 0: # x是N的因子 # 如果存在一种操作能让对手进入必败态则当前必胜 if not canWin(N - x): return True # 所有操作都无法让对手必败则当前必败 return False这个递归解法逻辑正确但存在大量的重复计算效率极低。例如计算canWin(10)时会计算canWin(9)、canWin(8)...而这些子问题在计算其他N时又会被重复计算。这正是动态规划DP大显身手的地方。我们可以用一个数组dp来记录每个N的状态dp[i]表示当数字为i时当前玩家是否必胜True/False。动态规划的思路定义状态dp[i]i从 1 到N。初始状态dp[1] False数字1无法操作必败。状态转移对于i从 2 到N我们需要判断dp[i]。遍历所有i的因子x1 x i且i % x 0。如果存在一个x使得dp[i - x] False即对手处于必败态那么dp[i] True当前玩家必胜。如果所有这样的x对应的dp[i - x]都是True那么dp[i] False当前玩家必败。最终答案dp[N]即为先手玩家爱丽丝的胜负情况。基于这个思路我们可以写出清晰的动态规划解法class Solution: def divisorGame(self, N: int) - bool: if N 1: return False # dp[i] 表示数字为i时当前操作者是否必胜 dp [False] * (N 1) # dp[0]无用从dp[1]开始 dp[1] False # N1必败 for i in range(2, N 1): # 遍历所有可能的因子x for x in range(1, i): if i % x 0: # 如果存在一种操作能让对手进入必败态则当前必胜 if not dp[i - x]: dp[i] True break # 找到一个必胜策略即可跳出循环 # 如果循环完整结束都没有找到必胜策略dp[i]保持初始的False即为必败 return dp[N]这个解法的时间复杂度是 O(N²)因为对于每个i最坏要遍历i-1次空间复杂度是 O(N)。对于力扣的题目限制N 1000完全足够也清晰地展示了从游戏规则到DP状态转移的完整逻辑。3. 跳出DP框架发现数学规律的本质动态规划解法已经足够好但如果你在纸上多推导几个N的dp值可能会发现一个有趣的模式N1: False (必败)N2: True (必胜) - 爱丽丝选x1N变成1必败态给鲍勃。N3: False (必败) - 因子只有1N-12必胜态给鲍勃。N4: True (必胜) - 可以选x1给鲍勃3-必败态也可以选x2给鲍勃2-必胜态。聪明人选x1。N5: False (必败) - 因子只有1N-14必胜态给鲍勃。N6: True (必胜) - 可以选x1给5-必败态选x2给4-必胜态选x3给3-必败态。选1或3都能赢。观察一下N为 2, 4, 6 时先手胜为 1, 3, 5 时先手负。这似乎暗示当N为偶数时先手爱丽丝必胜当N为奇数时先手必败。为什么这需要一点数学归纳的思维终极必败态N1奇数无法操作是公认的必败态。奇数的因子一个奇数的所有因子除了1和自身都是奇数吗不但一个奇数不可能被偶数整除0除外。因此一个奇数N的所有真因子x必然都是奇数。奇 - 奇 偶如果N是奇数x也是奇数那么N - x必然是偶数。关键推论当N是奇数时当前玩家无论是谁的任何合法操作都会将一个奇数N变成一个偶数(N-x)留给对手。反之偶数的因子一个偶数N至少有一个因子是 1奇数它可以选择x1那么N-1就变成了一个奇数留给对手。游戏进程推演如果爱丽丝开局拿到偶数N她总可以选择x1把一个奇数(N-1)扔给鲍勃。轮到鲍勃时他面对一个奇数。根据第4点他无论怎么操作都只能还给爱丽丝一个偶数。如此循环爱丽丝永远面对偶数她永远有x1这个“安全操作”可用可以持续把奇数扔给鲍勃。而鲍勃永远面对奇数他只能制造偶数给爱丽丝。数字N在严格递减因为x1最终鲍勃会面对那个终极奇数1无路可走输掉游戏。因此整个游戏的胜负在N确定的那一刻就决定了偶数先手必胜奇数先手必败。这是一个非常简洁优美的数学结论。4. 从解题到掌握博弈类问题的通用思考框架“除数博弈”这道题的价值远不止于记住“偶数赢奇数输”这个结论。它提供了一个处理一大类博弈问题的通用思考框架。当你再遇到类似“两人轮流操作无法操作者输”的题目时可以按以下路径分析第一步识别游戏类型是否是“公平组合游戏”Impartial Combinatorial Game即规则对双方是否完全对称且无随机性。“除数博弈”、“取石子游戏”Nim等都属于此类。第二步定义状态与胜负态将游戏局面定义为一个或多个状态变量如“除数博弈”中的数字N。明确最基本的“必败态”Terminal Position通常是无法进行任何合法操作的状态。用“必胜态/必败态”的逻辑去推理其他状态。第三步尝试寻找规律或状态转移方法A通用动态规划/记忆化搜索。这是最稳妥的方法尤其当状态空间有限时。就像我们写的DP解法定义dp[状态]从小状态开始递推或记忆化搜索大状态。方法B高效数学归纳/寻找规律。通过枚举小规模情况观察胜负是否与状态的某个数学属性奇偶性、模运算等强相关。就像我们发现的奇偶规律。这往往是问题设计精巧之处但DP是找到这个规律的有力工具。第四步验证与编码用DP验证你的数学猜想或者直接用DP实现。最终代码可能极其简单如return N % 2 0但推导过程体现的是你对问题本质的理解。回到“除数博弈”它的最终Python解答简单到令人惊讶class Solution: def divisorGame(self, N: int) - bool: # 偶数必胜奇数必败 return N % 2 0但请你务必明白这个一行代码的背后是博弈论的基本概念、动态规划的推导验证和数学归纳的深刻洞察。在面试或实际解决问题时展示出从暴力模拟到DP优化再到发现数学本质的完整思考链远比直接抛出答案更有价值。这类问题训练的不是记忆结论而是将模糊的游戏规则转化为清晰的可计算状态模型的能力。这种能力在解决更复杂的资源调度、策略选择等问题时至关重要。所以下次再看到类似的轮流操作题别慌先问问自己这个游戏的“状态”是什么“必败态”是什么状态之间如何转移 
长河君 · 2026/9/1 21:24:25 · 阅读 1.2k 从力扣1025题“除数博弈”解析博弈论与动态规划解题思路
最近在整理算法笔记时翻到了力扣第1025题“除数博弈”。这道题乍一看是个游戏规则简单但很多朋友第一次做的时候要么是硬着头皮去模拟游戏过程要么是尝试找规律但心里没底。题目描述是爱丽丝和鲍勃轮流玩游戏初始时有一个数字N。轮到谁时谁就选择一个x满足0 x N且N % x 0然后用N - x替换黑板上的数字N。如果轮到某个玩家时无法进行任何操作则判该玩家输。游戏规则清晰但直接去模拟每一步的选择对于稍大的N来说状态空间会非常复杂。这其实是一个典型的“博弈论”问题更具体地说是“公平组合游戏”中的一种。这类问题往往有一个共同点最终的胜负在游戏开始时就已经由初始状态决定了与玩家的具体操作无关。理解这一点是解决这类问题的关键。很多人会陷入一个误区认为必须去穷举所有可能的游戏路径才能判断胜负。但实际上对于“除数博弈”这类游戏我们真正需要关注的不是“怎么走”而是“当前状态是必胜态还是必败态”。一旦掌握了这个核心问题就会从一个复杂的模拟游戏简化成一个清晰的数学或动态规划问题。1. 先别急着写代码理解“必胜态”与“必败态”在公平组合游戏中双方操作规则相同且没有随机因素任何一个状态都可以被定义为“必胜态”或“必败态”。必胜态 (N-position)当前玩家有办法通过一次操作将游戏状态转移到一个“必败态”留给对手。必败态 (P-position)当前玩家所有可能的操作都会将游戏状态转移到一个“必胜态”留给对手。游戏的终止状态即无法操作的状态是必败态。因为轮到你了你却无路可走你输了。对于“除数博弈”当N 1时没有满足0 x 1的整数x当前玩家无法操作所以N1是必败态。我们的目标是判断N初始为某个数时先手玩家爱丽丝是否处于必胜态。那么如何判断一个N是必胜态还是必败态呢推理过程如下如果当前N是必败态那么爱丽丝先手就输了。如果当前N是必胜态那么爱丽丝就赢了。判断N的状态需要看是否存在一个xN的正因子且不等于N使得N - x这个新状态是必败态。如果存在这样的x那么爱丽丝就可以选择这个x把必败态扔给鲍勃自己稳操胜券。此时N是必胜态。如果所有可能的x对应的N - x都是必胜态那么无论爱丽丝怎么选都会把必胜态留给鲍勃自己就输了。此时N是必败态。这个过程天然形成了一个递归或动态规划的求解思路。我们可以从小到大地推导出每个N的状态。2. 从暴力递归到动态规划理清状态转移最直观的想法是写一个递归函数canWin(N)判断当前数字N是否必胜。def canWin(N): # 基础情况N1时无法操作必败 if N 1: return False # 遍历所有可能的操作x for x in range(1, N): if N % x 0: # x是N的因子 # 如果存在一种操作能让对手进入必败态则当前必胜 if not canWin(N - x): return True # 所有操作都无法让对手必败则当前必败 return False这个递归解法逻辑正确但存在大量的重复计算效率极低。例如计算canWin(10)时会计算canWin(9)、canWin(8)...而这些子问题在计算其他N时又会被重复计算。这正是动态规划DP大显身手的地方。我们可以用一个数组dp来记录每个N的状态dp[i]表示当数字为i时当前玩家是否必胜True/False。动态规划的思路定义状态dp[i]i从 1 到N。初始状态dp[1] False数字1无法操作必败。状态转移对于i从 2 到N我们需要判断dp[i]。遍历所有i的因子x1 x i且i % x 0。如果存在一个x使得dp[i - x] False即对手处于必败态那么dp[i] True当前玩家必胜。如果所有这样的x对应的dp[i - x]都是True那么dp[i] False当前玩家必败。最终答案dp[N]即为先手玩家爱丽丝的胜负情况。基于这个思路我们可以写出清晰的动态规划解法class Solution: def divisorGame(self, N: int) - bool: if N 1: return False # dp[i] 表示数字为i时当前操作者是否必胜 dp [False] * (N 1) # dp[0]无用从dp[1]开始 dp[1] False # N1必败 for i in range(2, N 1): # 遍历所有可能的因子x for x in range(1, i): if i % x 0: # 如果存在一种操作能让对手进入必败态则当前必胜 if not dp[i - x]: dp[i] True break # 找到一个必胜策略即可跳出循环 # 如果循环完整结束都没有找到必胜策略dp[i]保持初始的False即为必败 return dp[N]这个解法的时间复杂度是 O(N²)因为对于每个i最坏要遍历i-1次空间复杂度是 O(N)。对于力扣的题目限制N 1000完全足够也清晰地展示了从游戏规则到DP状态转移的完整逻辑。3. 跳出DP框架发现数学规律的本质动态规划解法已经足够好但如果你在纸上多推导几个N的dp值可能会发现一个有趣的模式N1: False (必败)N2: True (必胜) - 爱丽丝选x1N变成1必败态给鲍勃。N3: False (必败) - 因子只有1N-12必胜态给鲍勃。N4: True (必胜) - 可以选x1给鲍勃3-必败态也可以选x2给鲍勃2-必胜态。聪明人选x1。N5: False (必败) - 因子只有1N-14必胜态给鲍勃。N6: True (必胜) - 可以选x1给5-必败态选x2给4-必胜态选x3给3-必败态。选1或3都能赢。观察一下N为 2, 4, 6 时先手胜为 1, 3, 5 时先手负。这似乎暗示当N为偶数时先手爱丽丝必胜当N为奇数时先手必败。为什么这需要一点数学归纳的思维终极必败态N1奇数无法操作是公认的必败态。奇数的因子一个奇数的所有因子除了1和自身都是奇数吗不但一个奇数不可能被偶数整除0除外。因此一个奇数N的所有真因子x必然都是奇数。奇 - 奇 偶如果N是奇数x也是奇数那么N - x必然是偶数。关键推论当N是奇数时当前玩家无论是谁的任何合法操作都会将一个奇数N变成一个偶数(N-x)留给对手。反之偶数的因子一个偶数N至少有一个因子是 1奇数它可以选择x1那么N-1就变成了一个奇数留给对手。游戏进程推演如果爱丽丝开局拿到偶数N她总可以选择x1把一个奇数(N-1)扔给鲍勃。轮到鲍勃时他面对一个奇数。根据第4点他无论怎么操作都只能还给爱丽丝一个偶数。如此循环爱丽丝永远面对偶数她永远有x1这个“安全操作”可用可以持续把奇数扔给鲍勃。而鲍勃永远面对奇数他只能制造偶数给爱丽丝。数字N在严格递减因为x1最终鲍勃会面对那个终极奇数1无路可走输掉游戏。因此整个游戏的胜负在N确定的那一刻就决定了偶数先手必胜奇数先手必败。这是一个非常简洁优美的数学结论。4. 从解题到掌握博弈类问题的通用思考框架“除数博弈”这道题的价值远不止于记住“偶数赢奇数输”这个结论。它提供了一个处理一大类博弈问题的通用思考框架。当你再遇到类似“两人轮流操作无法操作者输”的题目时可以按以下路径分析第一步识别游戏类型是否是“公平组合游戏”Impartial Combinatorial Game即规则对双方是否完全对称且无随机性。“除数博弈”、“取石子游戏”Nim等都属于此类。第二步定义状态与胜负态将游戏局面定义为一个或多个状态变量如“除数博弈”中的数字N。明确最基本的“必败态”Terminal Position通常是无法进行任何合法操作的状态。用“必胜态/必败态”的逻辑去推理其他状态。第三步尝试寻找规律或状态转移方法A通用动态规划/记忆化搜索。这是最稳妥的方法尤其当状态空间有限时。就像我们写的DP解法定义dp[状态]从小状态开始递推或记忆化搜索大状态。方法B高效数学归纳/寻找规律。通过枚举小规模情况观察胜负是否与状态的某个数学属性奇偶性、模运算等强相关。就像我们发现的奇偶规律。这往往是问题设计精巧之处但DP是找到这个规律的有力工具。第四步验证与编码用DP验证你的数学猜想或者直接用DP实现。最终代码可能极其简单如return N % 2 0但推导过程体现的是你对问题本质的理解。回到“除数博弈”它的最终Python解答简单到令人惊讶class Solution: def divisorGame(self, N: int) - bool: # 偶数必胜奇数必败 return N % 2 0但请你务必明白这个一行代码的背后是博弈论的基本概念、动态规划的推导验证和数学归纳的深刻洞察。在面试或实际解决问题时展示出从暴力模拟到DP优化再到发现数学本质的完整思考链远比直接抛出答案更有价值。这类问题训练的不是记忆结论而是将模糊的游戏规则转化为清晰的可计算状态模型的能力。这种能力在解决更复杂的资源调度、策略选择等问题时至关重要。所以下次再看到类似的轮流操作题别慌先问问自己这个游戏的“状态”是什么“必败态”是什么状态之间如何转移