---

1510. 石子游戏 IV

• 标签：数学、动态规划、博弈
• 难度：困难

题目链接

• 1510. 石子游戏 IV - 力扣

题目大意

描述：Alice 和 Bob 轮流玩一个游戏。开始时有一堆 $n$ 个石子。每轮玩家可以移除完全平方数个石子（如 $1, 4, 9, 16, \dots$）。无法移除的玩家输。Alice 先手。

要求：判断 Alice 是否能获胜。

说明：

• $1 \le n \le 10^5$。

示例：

• 示例 1：

输入：n = 1
输出：true
解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。

• 示例 2：

输入：n = 2
输出：false
解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。

解题思路

思路 1：DP

1. 核心思想

这是一个公平组合博弈。定义 $dp[i]$ 表示 $i$ 个石子时先手是否能获胜。

转移：如果存在一个平方数 $j^2 \le i$，使得 $dp[i - j^2] == False$（即对手在剩余石子中必败），则 $dp[i] = True$。

2. 具体步骤

第 1 步：预计算所有 $\le n$ 的平方数。

第 2 步：$dp[0] = False$（没有石子时先手输）。

第 3 步：$i = 1 \to n$：

• 遍历平方数 $j^2 \le i$：
  • 如果 $dp[i - j^2] == False$：$dp[i] = True$，跳出。

第 4 步：返回 $dp[n]$。

3. 举例说明

以 $n = 7$ 为例：

• $dp[0] = False$
• $dp[1] = True$（拿 $1$）
• $dp[2] = False$（只能拿 $1$，$dp[1]=True$）
• $dp[3] = True$（拿 $1$，$dp[2]=False$）
• $dp[4] = True$（拿 $4$，$dp[0]=False$，或拿 $1$，$dp[3]=True$）
• $dp[5] = False$（拿 $4 \to dp[1]=True$，拿 $1 \to dp[4]=True$，均使对手胜）
• $dp[6] = True$（拿 $1$，$dp[5]=False$）
• $dp[7] = False$（拿 $4 \to dp[3]=True$，拿 $1 \to dp[6]=True$）

$n=7$ 时 Alice 输。

思路 1：代码

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        dp = [False] * (n + 1)
        squares = [i * i for i in range(1, int(n ** 0.5) + 1)]

        for i in range(1, n + 1):
            for sq in squares:
                if sq > i:
                    break
                if not dp[i - sq]:
                    dp[i] = True
                    break

        return dp[n]

思路 1：复杂度分析

• 时间复杂度：$O(n \sqrt{n})$，每个状态遍历平方数。
• 空间复杂度：$O(n)$。