[LeetCode] 1025. Divisor Game

[grandyang]

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number N on the chalkboard.  On each player's turn, that player makes a  move  consisting of:

• Choosing any x with 0 < x < N and N % x == 0.
• Replacing the number N on the chalkboard with N - x.

Also, if a player cannot make a move, they lose the game.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example 1:

Input: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Note:

1. 1 <= N <= 1000

这道题说是爱丽丝和鲍勃在玩一个除数游戏，这爱丽丝和鲍勃估计就相当于我们的小明和小红，或者是李雷和韩梅梅之类的吧，经常出现啊。说是最初有一个数字N，每次每个人选一个小于N且能整除N的数字x，并将N替换为 N-x，依次进行，直到某个人没法进行了，则算输了。现在给个任意的N，且爱丽丝先走，问爱丽丝能否赢得游戏。先来分析一个下得到什么数字的时候会输，答案是当N变成1的时候，此时没法找到小于N的因子了，则输掉游戏。博主看到题后的第一个反应就是用递归，因为调用递归得到的结果是对手的胜负，若递归返回 false，则说明当前选手赢了，反之则当前选手输了。但是递归的方法不幸超时了，因为有大量的重复计算在里面，我们需要缓存这些中间变量，以避免重复计算，可以使用递归加记忆数组来做，也可以使用迭代的写法，那么就变成动态规划 Dynamic Programming 了。这里的 dp 数组定义很直接，dp[i] 表示起始数字为i时爱丽丝是否会赢，大小为 N+1，更新时从2开始就行，因为0和1都是 false，从2更新到N，对于每个数字，都从1遍历到该数字，找小于该数的因子，不能整除的直接跳过，能整除的看 dp[i-j] 的值，若为 false，则 dp[i] 更新为 true，并 break 掉即可，参见代码如下：

解法一：

class Solution {
public:
    bool divisorGame(int N) {
        vector<bool> dp(N + 1);
        for (int i = 2; i <= N; ++i) {
            for (int j = 1; j < i; ++j) {
                if (i % j != 0) continue;
                if (!dp[i - j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[N];
    }
};

其实这道题的终极解法就一行，直接判断奇偶即可，若N是偶数爱丽丝一定能赢，奇数一定会输。博主大概讲一下原因吧，前面提到过了，若某个人拿到了1，则表示输了，所以当拿到2的时候，一定会赢，因为取个因数1，然后把剩下的1丢给对手就赢了。对于大于2的N，最后都会先减小到2，所以其实这个游戏就是个争2的游戏。对于一个奇数N来说，小于N的因子x一定也是个奇数，则留给对手的 N-x 一定是个偶数。而对于偶数N来说，我们可以取1，然后变成一个奇数丢给对手，所以拿到偶数的人，将奇数丢给对手后，下一轮自己还会拿到偶数，这样当N不断减小后，最终一定会拿到2，所以会赢，参见代码如下：

解法二：

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

Github 同步地址:

#1025

参考资料：

https://leetcode.com/problems/divisor-game/

https://leetcode.com/problems/divisor-game/discuss/274608/Simple-DP-Java-Solution

https://leetcode.com/problems/divisor-game/discuss/296784/Come-on-in-different-explanation-from-others

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

解法一可以做一个优化，i 的factor 只需要从 1到 sqrt(i), factor就是
j 和 i/j

[grandyang]

解法一可以做一个优化，i 的factor 只需要从 1到 sqrt(i), factor就是
j 和 i/j

求贴代码