1025. Divisor Game 除数博弈


作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/


@TOC

题目地址:https://leetcode.com/problems/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:

  1. Choosing any x with 0 < x < N and N % x == 0.
  2. 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 <= N <= 1000

题目大意

对于数字N,做两个操作:1. 找出一个因数x,2. 把N换成N - x。两个人轮流做这个操作,问第一个人是否能赢。

解题方法

找规律

首先说结论:当N是偶数时第一个人一定赢,当N是奇数时第一个一定输。

  1. 奇数的因子只有奇数,偶数的因子至少一个偶数2
  2. 奇数 - 奇数 = 偶数
  3. 当Alice的值是N时必输,则当Alice的值是N+1时必赢(拿1即可)

那么,当N为下列数字时,先发的状态如下。 当N=1,输; 当N=2,赢(性质3); 当N=3,输(性质1和2,对方一定是偶数,上面的偶数情况都赢); 当N=4,赢(性质3); 当N=5,输(性质1和2,对方一定是偶数,上面的偶数情况都赢); ... 所以,N为偶数都赢,N为奇数都输。

C++代码如下:

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

动态规划

动态规划就是很朴素的做法了,对每个位置i,遍历其因数x,判断N-x的状态,当N-x为输的时候自己赢。

C++代码如下:

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

参考资料:https://leetcode.com/problems/divisor-game/discuss/368269/C%2B%2B-100-and-96-and

日期

2019 年 8 月 30 日 —— 赶在月底做个题