题目描述

最初，黑板上有一个数字$N$。在每个玩家的回合，玩家需要执行以下操作：

选出任一x，满足$0 < x < N$ 且$N$ % $x$ == $0$。
用 $N - x$替换黑板上的数字 $N$ 。
如果玩家无法执行这些操作，就会输掉游戏。

样例

3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作

算法1

(数学家表示已经知道了答案) $O(C)$

def divisorGame(self, N: int) -> bool:
    return N%2==0

归纳法：

数字N如果是奇数，它的约数必然都是奇数；若为偶数，则其约数可奇可偶。
无论N初始为多大的值，游戏最终只会进行到N=2时结束，那么谁轮到N=2时谁就会赢。
因为爱丽丝先手，N初始若为偶数，爱丽丝则只需一直选1，使鲍勃一直面临N为奇数的情况，这样爱丽丝稳赢；
N初始若为奇数，那么爱丽丝第一次选完之后N必为偶数，那么鲍勃只需一直选1就会稳赢。
综述，判断N是奇数还是偶数，即可得出最终结果！

算法2

($DP$) $O(n^2)$

Py 代码

def divisorGame(self, N: int) -> bool:
        target = [0 for i in range(N+1)]
        target[1] = 0 #若爱丽丝抽到1，则爱丽丝输
        if N<=1:
            return False
        else:

            target[2] = 1 #若爱丽丝抽到2，则爱丽丝赢
            for i in range(3,N+1):
                for j in range(1,i//2):
                    # 若j是i的余数且target[i-j]为假（0）的话，则代表当前为真（1）
                    if i%j==0 and target[i-j]==0:
                        target[i] = 1
                        break
            return target[N]==1

简洁点:

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