T1510.石子游戏 IV

game theory, dp, https://leetcode.cn/problems/stone-game-iv/

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

这道题是一个典型的博弈论 + 动态规划（Dynamic Programming）问题。

解题思路

定义状态： 我们可以定义一个布尔型数组 dp，其中 dp[i] 表示当面对剩下 i 个石子时，当前玩家（轮到操作的人）是否必胜。
- dp[i] = True：表示当前玩家必胜。
- dp[i] = False：表示当前玩家必败。
基本情况（Base Case）：
- dp[0] = False：如果没有石子了，当前玩家无法操作，直接输掉。
状态转移方程： 对于剩下的 i 个石子，当前玩家可以拿走 $k^{2}$ 个石子（其中 $k \geq 1$ 且 $k^{2} \leq i$ ）。拿走 $k^{2}$ 个石子后，石子数量变成 i - k^2，轮到对手操作。
- 如果对手在 i - k^2 的状态下是必败的（即 dp[i - k*k] == False），那么当前玩家只要选择拿走 $k^{2}$ 个石子，就能把必败的状态留给对手，从而让自己获得胜利！
- 因此，只要存在任意一个 $k$ ，满足 dp[i - k*k] == False，那么 dp[i] 就可以设为 True，并且可以直接停止继续寻找（因为已经找到了获胜策略）。
- 如果尝试了所有可能的 $k^{2}$ ，发现对手在所有 i - k*k 状态下都是必胜的（即 dp[i - k*k] == True），那么当前玩家无论怎么选都会输，所以 dp[i] = False。

Python 代码实现

python

class Solution:

    def winnerSquareGame(self, n: int) -> bool:
        # dp[i] 表示面对 i 个石子时，当前操作的人是否必胜
        dp = [False] * (n + 1)

        # 从 1 个石子推导到 n 个石子
        for i in range(1, n + 1):
            k = 1
            while k * k <= i:
                # 如果拿走 k*k 个石子后，对手处于必败状态
                if not dp[i - k * k]:
                    dp[i] = True
                    break  # 只要找到一种必胜策略，即可停止尝试其他的平方数
                k += 1

        return dp[n]

复杂度分析

时间复杂度： $O (n \sqrt{n})$
- 外层循环运行 $n$ 次。
- 内层循环对于每个 $i$ ，最多运行 $\sqrt{i}$ 次。
- 总时间复杂度为 $\sum_{i = 1}^{n} \sqrt{i} \approx \frac{2}{3} n^{1.5}$ 。当 $n = 10^{5}$ 时，计算次数约为 $3 \times 10^{7}$ 次，可以在 Python 中轻松通过（限时通常为 1 秒）。
空间复杂度： $O (n)$
- 需要一个长度为 $n + 1$ 的布尔数组 dp 保存状态。

T1510.石子游戏 IV ​

T1510.石子游戏 IV