1025. Divisor Game

QUESTION:

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

EXPLANATION:

这题的意思很明确了。就是两个人进行博弈，同时两者都是理性的。

那么就很简单了，不是A赢就是B赢。

那我们就可以用一个数组来记录A赢的情况，A赢的情况的反面其实就B赢。

那么[1] 是A输，那么就是false。

[2]我们可以怎么计算呢，那么就是A可以只取一个，那么这时候，就剩下了tmp[1]是false，那么B就必然是输了。所以[2]就是true。

[3]的情况我们可以考虑到就是没有办法只能是输，结果为false。

那么问题就可以转化为：A可不可以拿出一个数，正好是B输的情况。

SOLUTION:

class Solution {
    public boolean divisorGame(int N) {
        boolean[] temp = new boolean[N + 1];
        temp[1] = false;
        for (int i = 2; i <= N; i++) {//填充整个数组
            for (int j = 1; j < i; j++) {//遍历可能的x的值
                if (i % j == 0 && !temp[i - j]) {//如果x符合条件，既能整除，同时能让B输。
                    temp[i] = true;
                    break;
                }
            }
        }
        return temp[N];
    }
}
--> return <--