爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

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

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

    只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。

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

    // 归纳法
    分析：如果N是一个偶数，先手开局的人直接1, 使得N-1变成奇数；
    1、对于奇数(>2)分两种情况：
    1.1： 奇数且为质数，则只能选择x=1, 此时N-1变成偶数；
    1.2： 奇数且不为质数，则能被奇数整除数c的还是奇数，此时N-c变为偶数；

    用A与B分别表示爱丽丝和鲍勃：
    (1): 如果N是偶数，则A会选x=1使得N=N-x变成奇数，迫使B只能选c使得N=N-c变成偶数；直到最后N变成2,则A选择1，胜出；
    (2): 如果N是奇数，则A只能选择x=c使得N=N-c变成偶数，此时B按照(1)中A的策略，不断的选x=1, 直到最后N=2时候，轮到B选择，此时B取x=1胜出。
    综上：如果N是偶数，则A按照策略(1)会胜出；如果N为奇数，则B按照策略(2)会胜出。

    1. bool divisorGame(int N) {
    2.     return N%2 == 0;
    3. }

    // 动态规划
    经过前面的分析，可以采用递推的方式预测游戏的胜负；
    用dp[i]记录从1到N的每一个数字胜出的对象,如果dp[i]为1表示爱丽斯胜出，如果dp[i]为0表示爱丽斯输掉；
    可以知道，如果在每一步的选择x的过程中，使得在i-x能保证对方输掉dp[i-x]为0(满足i%x==0)，则选手会直接进行取该x;

    bool divisorGame(int N){
    vector<int> dp(N+2, 0);   // dp记录爱丽斯是否胜出
    dp[1] = 0;
    dp[2] = 1;                // 考虑N=1的情况下，dp[2]出错
    for(int i=3; i<=N; ++i){
        for(int x=1; x < i; ++x){
            if (i % x == 0 && !dp[i-x])
            {
                dp[i] = 1;
                break;
            }
        }   
    }
    return dp[N];
}