LeetCode 1025简单动态规划
除数博弈 图解题解
这道题到底在问什么
爱丽丝和鲍勃轮流玩游戏，爱丽丝先手。黑板上最初有数字 n，且 1 <= n <= 1000。每回合，玩家选择整数 x，满足 0 < x < n 且 n % x == 0，然后把 n 替换为 n - x。无法执行操作的人输。假设双方都以最佳状态参与，只有爱丽丝获胜时返回 true。
- 输入
- n = 2
- 输出
- true
- 解释
- 爱丽丝选择 1，n 变成 1，鲍勃无法操作。
- 输入
- n = 3
- 输出
- false
最优解：一步一步想明白
- 3先用 DP 把胜负态推出来，再观察奇偶规律，比直接背 n%2 更可靠。
- 4从 n=1 这个必败态开始，奇偶胜负会交替固定下来。
- 5dp = [False] * (n + 1)表格每一列就是一个 dp[i]，这一行的布尔值表示“当前先手玩家面对数字 i 能不能赢”。i=1 时不存在任何满足 0 < x < 1 的整数，所以当前玩家无法操作，dp[1]=false。
- 6for x in range(1, i):只要能把对手送到一个必败态，当前 i 就是必胜态。
- 7if i % x == 0 and not dp[i - x]:3 只能把 2 交给对手，而 2 是对手的必胜态，所以 dp[3]=False。
- 8dp[i] = True; breakDP 里一旦找到能让对手输的 x，就可以 break。
- 9for x in range(1, i):5 是奇数，合法真因子是奇数；奇数减奇数会变偶数，也就是把必胜态交给对手。
- 10if i % x == 0 and not dp[i - x]:偶数不需要找复杂因子，选 x=1 就能把奇数必败态留给对手。
- 11odd -> even；even -> odd从 1 输开始，奇数全是必败态，偶数全是必胜态。
- 12return n % 2 == 0DP 表推到这里已经能看出奇偶规律，优化版代码可以直接写 return n % 2 == 0。
- 13DP 表不是只展示结果：每个 True 都来自代码里找到某个 x，使得下一步 i-x 是对手必败态。
- 14这不是只观察了 1 到 6，而是由奇偶变化的归纳规则推出所有 n 的胜负。
- 17这题可以用 DP 验证，但上线代码用数学规律更直接。
⚠️ 容易写错的地方
✗ 错：n=1 返回 true
✓ 对：n=1 返回 false
没有合法的 x 可以选。
✗ 错：写递归搜索所有因子
✓ 对：直接用奇偶规律
本题胜负态有稳定数学结论。
✗ 错：以为偶数要选最大因子
✓ 对：偶数选 1 就够
目标是把奇数必败态留给对手。
完整代码（Python）
Python
class Solution:
def divisorGame(self, n):
dp = [False] * (n + 1)
for i in range(2, n + 1):
for x in range(1, i):
if i % x == 0 and not dp[i - x]:
dp[i] = True
break
return dp[n]复杂度
时间复杂度
O(n²)
DP 推导版枚举 i 和候选因子 x；n <= 1000，可以通过。规律优化版是 O(1)。
空间复杂度
O(n)
DP 推导版保存胜负表；规律优化版是 O(1)。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 除数博弈 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「动态规划」，换最直接的暴力解会差在哪？+
动态规划抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。