1025. Divisor Game

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation