前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、除数博弈

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

　　１、选出任一 x，满足 0 < x < N 且 N % x == 0 。

　　２、用 N - x 替换黑板上的数字 N 。

如果玩家无法执行这些操作，就会输掉游戏。只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。

示例 1：

输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。

示例 2：

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

1.1、解题思路

先找规律，再想办法动态规划

1.2、算法

1.2.1、算法1

N = 1 的时候，区间 (0,1) 中没有整数是 n 的因数，所以此时 Alice 败。

N = 2 的时候，Alice 只能拿 1，N 变成 1，Bob 无法继续操作，故 Alice 胜。

N = 3 的时候，Alice 只能拿 1，N 变成 2，根据 N=2 的结论，我们知道此时 Bob 会获胜，Alice 败。

N = 4 的时候，Alice 能拿 1 或22，如果 Alice 拿 1，根据 N=3 的结论，Bob 会失败，Alice 会获胜。

N = 5 的时候，Alice 只能拿 1，根据 N=4 的结论，Alice 会失败。

推理： 从 4 和 5 开始，其实也可以看出来，当第一个人选择之后，生效的数字其实已经遍历过了，比如

N = 4的时候，

　　　　　　第一个人选择 1，则第二个人开始选择（此时N = 3），则这个时候，后面选择的人会赢

　　　　　　第一个人选择 2，则第二个人开始选择（此时 N = 2），则这个时候，先选择的会赢，

　　　　　　所以， Alice 选择1的时候，必赢。

N = 5 的时候，同上理论

N 为奇数的时候 Alice（先手）必败，N 为偶数的时候 Alice 必胜

/** 爱丽丝为 偶数肯定能赢 */
public boolean divisorGame2(int N) {
    return N % 2 == 0;
}

1.2.2、算法2

public boolean divisorGame(int N) {

    if (N ==1){
        return false ;
    }

    boolean[] dp = new boolean[N + 1];

    dp[1] = false;
    dp[2] = true;
    for (int i = 3; i <= N; ++i) {
        //j 从1开始不会超过i
        for (int j = 1; j < i; ++j) {
            // f[i-j] 为后面的人肯定会输false 时，当前人会赢
            if ((i % j) == 0 && !dp[i - j]) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[N];
}

1.3、测试

@Test
public void test(){
    System.out.println(divisorGame(10));
}

​