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];
    }
}