1025. 除数博弈

Easy

题目描述

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

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

• 选择任意一个整数 x，满足 0 < x < n 且 n % x == 0。
• 用 n - x 替换黑板上的数字 n。

如果玩家无法执行有效的移动，则该玩家败北。

只有在爱丽丝在游戏中取胜时才返回 true。假设两个玩家都以最佳状态参与游戏。

示例 1：

输入：n = 2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行有效移动。

示例 2：

输入：n = 3
输出：false
解释：爱丽丝选择 1，鲍勃选择 1，爱丽丝无法进行有效移动。

提示：

• 1 <= n <= 1000

解题思路

这道题有两种解法思路：

方法一：数学规律（推荐）

通过分析游戏规律可以发现：

• 如果当前数字是偶数，当前玩家可以选择减去1，使得对手面对奇数
• 如果当前数字是奇数，当前玩家只能减去奇数因子，结果必然是偶数，对手又面对偶数

关键观察：奇数的所有因子都是奇数，偶数至少有因子1。因此：

• 面对偶数的玩家总是可以让对手面对奇数
• 面对奇数的玩家只能让对手面对偶数

由于爱丽丝先手，如果n是偶数，她可以一直保持让鲍勃面对奇数的状态，最终获胜；如果n是奇数，鲍勃会获得主动权。

方法二：动态规划

定义dp[i]表示当前数字为i时，当前玩家是否能获胜。状态转移：如果存在任一有效移动j使得dp[i-j]为false，则dp[i]为true。

基于题目的数据范围和规律性，数学方法更简洁高效。

代码实现

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

class Solution:
    def divisorGame(self, n: int) -> bool:
        return n % 2 == 0

public class Solution {
    public bool DivisorGame(int n) {
        return n % 2 == 0;
    }
}

/**
 * @param {number} n
 * @return {boolean}
 */
var divisorGame = function(n) {
    return n % 2 === 0;
};

复杂度分析