1025.除数博弈

题解(数学归纳法)

列举N=1 2 3 … 5的情况

发现当N为偶数，且两个玩家都以最佳状态参与游戏的时候爱丽丝必胜，N为奇数鲍勃必胜。可通过数学归纳法证明：

当N为1或N为2，结论成立。

• 当N为偶数，x为N的因数，可以是偶数也可以是奇数，那么爱丽丝取奇数，N-x就为奇数，且N-x<=k，爱丽丝必胜。
• 当N为奇数，x为N的因数，则只能是奇数，N-x只能是偶数，且N-x<=k，鲍勃必胜。

代码

class Solution {
    public boolean divisorGame(int N) {
        return N % 2 ==0;
    }
}      

题解(递推)

代码

class Solution {
    public boolean divisorGame(int N) {
        boolean[] f = new boolean[N+2];//因为列举f[2]= true 所以+2
        f[1] = false;
        f[2] = true;
        for(int i = 3; i <= N; i++){
            for(int j = 1; j < i; j++){
                if(i % j == 0 && !f[i-j]){
                    f[i] = true;
                    break;
                }
            }
        }
        return f[N];
    }
}