What is the core idea behind the Divisor Game?

The core idea is to subtract divisors from n, and the winner is the one who forces the opponent into a losing position by making optimal moves.

How can dynamic programming help solve this problem?

Dynamic programming is used to track winning and losing positions for each possible value of n, allowing us to efficiently compute the game's outcome.

Why is the parity of n important in the Divisor Game?

The parity determines the type of move a player can make. Alice can always subtract 1 when n is even, but when n is odd, Alice must subtract an odd divisor.

What would happen if there were more players involved?

With more players, the game would become more complex. Each player's strategy would need to be adapted to ensure a winning position, with new state transitions for each additional player.

What other patterns or algorithms are related to this problem?

This problem relates to game theory, dynamic programming, and state transitions. It is also linked to problems involving turn-based games and optimal strategies.

#1025

Easy

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

除数博弈

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：选出任一整数 x ，满足 0 且 n % x == 0 。用 n - x 替换黑板上的数字 n 。如果玩家无法执行这些操作，就会输掉游戏。只有在爱丽丝在游戏中取得胜利…

数学动态规划脑筋急转弯博弈论

题目描述

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

最初，黑板上有一个数字 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

lightbulb

解题思路

方法一：数学归纳法

当 $n=1$ ，先手败
当 $n=2$ ，先手拿 $1$ ，剩下 $1$ ，后手败，先手胜
当 $n=3$ ，先手拿 $1$ ，剩下 $2$ ，后手胜，先手败
当 $n=4$ ，先手拿 $1$ ，剩下 $3$ ，后手败，先手胜
...

猜想，当 $n$ 为奇数时，先手败；当 $n$ 为偶数时，先手胜。

证明：

若 $n=1$ 或 $n=2$ ，结论成立；
若 $n \gt 2$ $n > 2$ ，假设 $n \le k$ $n \leq k$ 时，该结论成立，则 $n=k+1$ $n = k + 1$ 时：
- 若 $k+1$ 为奇数，由于 $x$ 是 $k+1$ 的因数，那么 $x$ 只可能是奇数，因此 $k+1-x$ 为偶数，后手胜，先手败；
- 若 $k+1$ 为偶数，此时 $x$ 既可以是奇数 $1$ ，也可以是偶数，若 $x$ 取奇数，那么 $k+1-x$ 为奇数，后手败，先手胜。

综上，当 $n$ 为奇数时，先手败；当 $n$ 为偶数时，先手胜。结论正确。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

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

speed

复杂度分析

指标	值
时间	complexity depends on how efficiently we calculate divisors and transition states. The space complexity depends on the dynamic programming array size, which is O(n).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of game theory and dynamic programming concepts.
question_mark
Check if the candidate can optimize the approach beyond brute force.
question_mark
Assess the candidate’s ability to recognize patterns in state transitions.

warning

常见陷阱

外企场景

error
Not considering the impact of parity (even/odd) in game decisions.
error
Overcomplicating the problem by calculating all divisors instead of focusing on state transitions.
error
Failing to optimize space usage with dynamic programming.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend the problem to multiple players instead of just Alice and Bob.
arrow_right_alt
Consider the case where players can subtract any divisor instead of only the proper ones.
arrow_right_alt
Introduce a restriction on the number of moves a player can make.

help

常见问题

外企场景

继续练习

#913 猫和老鼠 #1140 石子游戏 II #877 石子游戏