除数博弈 图解题解

除数博弈这道题，先手到底靠什么赢

黑板上写着数字 n，Alice 先手。每步选一个真因子 j（能整除 n、又比 n 小的正整数），把 n 换成 n-j。谁轮到时 n 已是 1、没因子可减，谁就输。两人都最优，问先手 Alice 能否赢，题面 n=10 时她赢、返回 true。难在「双方都最优」：得算到对手接手后会不会反过来治你。

照规则一步步模拟对局，为什么会越算越慢

照规则递归模拟：轮到你把每个能减的真因子都试一遍，看哪步能把对手逼进必输；对手接手也要挨个试他的因子，一层套一层，局面数随 n 指数级膨胀。更亏的是同一局面被反复算——8 减 2、9 减 3 都落到 6，「面对 6 会怎样」被重判多次。病根是子局面重复计算。

从最小的局面倒推，dp[i] 记的到底是什么

既然子局面被反复算，就让每个只算一次、存下来，这就是动态规划（DP，把每个『面对数字 i 会怎样』的结论算一次存下、更大局面直接查）。定义 dp[i]：数字是 i、轮到你走能不能赢，能赢记 True、必输记 False。数字 1 没有更小的正因子可减，轮到谁谁走不了、直接输，dp[1]=False，是不必再往下拆的起点（base case，最简单、不用再推的情况）。从数字 2 起，每个 dp[i] 都由更小的已算局面推出。

存在一个因子能把对手推进必输，你就赢

面对数字 i，减掉真因子 j 后轮到对手：只要有一个 j 让 dp[i-j]=False（对手必输），你就赢定了，找到一个就够；反过来，每个因子减完落点 dp[i-j] 全是 True，你怎么走都是拱手让人，dp[i]=False。参考代码内层枚举 j，i%j==0 且 not dp[i-j] 一成立就置 dp[i]=True 并 break。

拿 n=10 把整张表从左往右填出来

一行格子，列号就是数字，先钉死 dp[1]=False。dp[2]：真因子只有 1，减 1 落到 dp[1]=False 对手必输，dp[2]=True（题面 n=2 返回 true）。dp[3]：减 1 落到 dp[2]=True、无别的因子可挑，dp[3]=False（n=3 返回 false）。dp[4]：减 1 落到 dp[3]=False，dp[4]=True。此后偶数格都能减 1 落到前一个必输的奇数、全为 True；奇数格减完只能落到能赢的偶数、全为 False。到 dp[10]=True，n=10 先手赢。

dp[1] 填错，为什么整张表会全反

dp[1] 手滑填成 True，dp[2] 会误判「减 1 落到对手能赢的局面」而算成 False，一路错到底、整张表全反，所以 dp[1]=False 这颗种子必须先钉死。复杂度上外层从 2 扫到 n、内层枚举因子最多 O(n) 个（大 O 记号形容规模变大时操作数大概怎么涨），合起来 O(n²)，空间 O(n)。另一坑是内层 j 只能取 0<j<i 的真因子，把 j=i 也算进去就减到 0、下标越界。本题另有 O(1) 规律解：n 偶数先手必赢、return n%2==0，但它为什么成立仍靠这张表。

Python

def divisorGame(n: int) -> bool:
    dp = [False] * (n + 1)   # dp[1]=False
    for i in range(2, n + 1):
        for j in range(1, i):
            if i % j == 0 and not dp[i - j]:
                dp[i] = True
                break
    return dp[n]

C++

bool divisorGame(int n){
    vector<bool> dp(n + 1, false);
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j < i; ++j)
            if(i % j == 0 && !dp[i - j]){
                dp[i] = true; break;
            }
    return dp[n];
}

Java

public boolean divisorGame(int n){
    boolean[] dp = new boolean[n + 1];
    for(int i = 2; i <= n; i++)
        for(int j = 1; j < i; j++)
            if(i % j == 0 && !dp[i - j]){
                dp[i] = true; break;
            }
    return dp[n];
}