1025. Divisor Game

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number N on the chalkboard. On each player's turn, that player makes a move consisting of:

• Choosing any x with 0 < x < N and N % x == 0.

• Replacing the number N on the chalkboard with N - x.

Also, if a player cannot make a move, they lose the game.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example 1:

Input: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Note:

1. 1 <= N <= 1000

觀察一下N = 1~4的情況，再由數學歸納法可以得知N是Odd時，玩家會輸，N是even時，玩家會獲勝。 N = 1, 玩家輸。 N = 2, 玩家贏。 N = 3, 玩家輸。 N = 4, 玩家贏。 假設N = 2k時，玩家贏，N = 2k + 1時，玩家輸。 (i) N = 2k, 該數可以有odd或者even的因數，這裡用odd_0和even_0表示。如果玩家選擇odd_0，那剩下的數N'為N - odd_0，為一個奇數。N'所有的因數都是奇數，這裡用odd_1表示。那麼f(N) = f(2k) = f(2k - odd_0 - odd_1) = f(even) = true。 (ii) N = 2k + 1, 該數只有odd的因數，這裡用odd_0表示。那麼N' = N - odd_0為一個偶數。N'可以有odd和even的因數，這裡用odd_1和even_1表示，這題假設大家都是聰明人，每次動作都是對自己最有利的，那麼對手會選擇odd_1，好讓留給玩家的是奇數。f(N) = f(2k + 1) = f(2k + 1 - odd_0 - odd_1) = f(odd) = false。

// Math
bool divisorGame(int N) {
    return N % 2 == 0;
}

可以利用Top-Down Recursion搭配memoization dp array去紀錄已經算過的結果避免重複。

// Top-Down Recursive DP
bool helper(int N, vector<int>& dp, bool res) {
    if (dp[N] != 0) return dp[N] == 1;
    for (int i = 1; !res && i * i < N; ++i) {
        if (N % i == 0) res = !helper(N - i, dp, res);
    }
    dp[N] = res ? 1 : -1;
    return res;
}
bool divisorGame(int N) {
    vector<int> dp(1001, 0);
    return helper(N, dp, false);
}

由Alice的角度loop所有i的可能，然後從比i小的數字中找出符合的因數j，檢查i - j是否會讓對手輸，如果會讓對手輸的話，Alice就會選這個數，然後再一直下去。

// Bottom-Up DP
bool divisorGame(int N) { // time: O(N^2); space: O(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) {
                if (!dp[i - j]) { // If Alice chooses i, and will let her opponent lose
                    dp[i] = true;
                    break;
                }
            }
        }
    }
    return dp[N];
}