算法

(DP) $O(n^2)$

Java 代码

class Solution {
    public boolean divisorGame(int N) {
        // dp[i]: i的当前回合玩家是否能获胜
        // dp[i] = !dp[i - x]  1<=x<i && i % x == 0
        // dp[1] = false
        boolean[] dp = new boolean[N + 1];
        for (int i = 2; i <= N; ++i) {
            for (int x = 1; x < i; ++x) {
                if (i % x == 0) dp[i] = !dp[i - x];
                if (dp[i]) break;
            }
        }
        return dp[N];
    }
}