石子游戏 IV

题目描述
Alice 和 Bob 轮流玩游戏，初始时有一堆石子，总数为 n。在每个回合中，玩家可以从当前石子堆中取走一个 完全平方数（即 1, 4, 9, 16, …）个石子。无法取石子的玩家输掉游戏。
假设 Alice 先手，两人都采用 最优策略。给定 n，判断 Alice 是否能赢得游戏。若返回 True 表示 Alice 必胜，否则返回 False。

示例

• 输入：n = 1
  输出：True
  解释：Alice 可以直接取走 1 个石子，Bob 无法操作，Alice 胜。
• 输入：n = 2
  输出：False
  解释：Alice 只能取 1（平方数只有 1），剩下 1 个给 Bob，Bob 取走最后 1 个，Alice 输。
• 输入：n = 4
  输出：True
  解释：Alice 可以直接取走 4 个石子获胜。

解题思路

这是一个 无偏组合博弈 问题，可通过 动态规划（或称为博弈 DP）解决。
由于每次操作仅与当前剩余石子数有关，可以定义状态 dp[i] 表示当剩余 i 个石子时，当前要行动的玩家是否必胜（True/False）。

状态转移分析

• 如果当前剩余 i 个石子，当前玩家可以取走的石子数为 k，其中 k 是平方数且 k ≤ i。
• 取走 k 个后，剩余 i-k 个石子轮到对方行动。
• 如果存在某个 k 使得 dp[i-k] == False（即对方在剩余 i-k 石子时必败），那么当前玩家取走 k 个就能让对方面临必败局面，因此 dp[i] = True。
• 如果所有可能的 k 都导致 dp[i-k] == True（即对方在剩余 i-k 石子时必胜），那么无论当前玩家怎么取，对方都能赢，因此 dp[i] = False。

初始化

• dp[0] = False：没有石子可取时，当前玩家失败。

计算顺序
从小到大计算 i = 1..n，对每个 i 枚举所有平方数 k ≤ i。

详细步骤

1. 预先计算出不超过 n 的所有完全平方数集合 squares。
2. 初始化 dp = [False] * (n+1)。
3. 遍历 i 从 1 到 n：
   • 对每个平方数 sq（满足 sq ≤ i）：
     • 如果 dp[i - sq] == False，则 dp[i] = True 并跳出循环（因为已经找到必胜策略）。
4. 返回 dp[n]。

举例说明（n=6）

• 平方数列表：1, 4
• dp[0] = False
• i=1: 只能取 1 → dp[0]=False → dp[1]=True
• i=2: 只能取 1 → dp[1]=True → 对方必胜 → dp[2]=False
• i=3: 取 1 → dp[2]=False → dp[3]=True
• i=4: 可取 1 或 4
  • 取 1 → dp[3]=True（对方胜）
  • 取 4 → dp[0]=False → 有方案使对方败 → dp[4]=True
• i=5: 取 1 → dp[4]=True；取 4 → dp[1]=True → 都使对方胜 → dp[5]=False
• i=6: 取 1 → dp[5]=False → 有方案使对方败 → dp[6]=True

最终 dp[6] = True，Alice 胜。

复杂度分析

• 时间复杂度：O(n√n)，因为对于每个 i 最多枚举 √i 个平方数。
• 空间复杂度：O(n)。

代码实现（Python）

def winnerSquareGame(n):
    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]

总结
本题通过 博弈 DP 将问题转化为：
当前状态是否 存在一种操作 使得对方处于必败状态。
这是一种典型的“必胜/必败”状态递推，在博弈类区间（或序列）动态规划中很常见。