LeetCode 题解工作台
石子游戏 IV
Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。 一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。 如果石子堆里没有石子了，则无法操作的玩家输掉游戏。 给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 ，表示当前石子堆中有 个石子时，当前玩家是否能赢得比赛。如果当前玩家能赢得比赛，则返回 ，否则返回 。那么答案即为 。 函数 的计算过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。
一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石子堆里没有石子了，则无法操作的玩家输掉游戏。
给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。
示例 1：
输入：n = 1 输出：true 解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。
示例 2：
输入：n = 2 输出：false 解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。
示例 3：
输入：n = 4 输出：true 解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。
示例 4：
输入：n = 7 输出：false 解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。 如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。 如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。
示例 5：
输入：n = 17 输出：false 解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。
提示：
1 <= n <= 10^5
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示当前石子堆中有 个石子时，当前玩家是否能赢得比赛。如果当前玩家能赢得比赛，则返回 ，否则返回 。那么答案即为 。
函数 的计算过程如下：
- 如果 ，说明当前玩家无法进行任何操作，因此当前玩家输掉比赛，返回 ；
- 否则，枚举当前玩家可以拿走的石子数量 ，其中 为平方数，如果当前玩家拿走 个石子后，另一个玩家无法赢得比赛，则当前玩家赢得比赛，返回 。如果枚举完所有的 ，都无法满足上述条件，则当前玩家输掉比赛，返回 。
为了避免重复计算，我们可以使用记忆化搜索，即使用数组 记录函数 的计算结果。
时间复杂度 ，空间复杂度 。其中 为石子堆中石子的数量。
class Solution:
def winnerSquareGame(self, n: int) -> bool:
@cache
def dfs(i: int) -> bool:
if i == 0:
return False
j = 1
while j * j <= i:
if not dfs(i - j * j):
return True
j += 1
return False
return dfs(n)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * sqrt(n)) because for each i from 1 to n we check up to sqrt(i) perfect square moves. Space complexity is O(n) to store the DP array representing winning and losing states for each pile size. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask if you considered precomputing squares to improve DP efficiency.
- question_mark
Expect you to explain how dp[i] = any(!dp[i - k*k]) captures winning states.
- question_mark
Check if you correctly handle edge cases like n = 0 or small perfect squares.
常见陷阱
外企场景- error
Failing to consider all possible perfect square moves for each state.
- error
Incorrectly initializing dp[0], leading to wrong outcomes for small n.
- error
Confusing the state meaning, marking dp[i] as true when it does not force a loss on the opponent.
进阶变体
外企场景- arrow_right_alt
Change the removal rule to cubes instead of squares to test DP adaptability.
- arrow_right_alt
Play with multiple piles and allow removing squares from any pile, increasing state space complexity.
- arrow_right_alt
Modify the first player to Bob and ask for the winning strategy under the same DP framework.