题目描述

Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。

一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

如果石子堆里没有石子了，则无法操作的玩家输掉游戏。

给你正整数 n，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True，否则返回 False。

样例

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

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

输入：n = 4
输出：true
解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。

输入：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）。

输入：n = 17
输出：false
解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。

限制

• 1 <= n <= 10^5

算法

(动态规划) $O(n \sqrt{n})$

1. 设 $f(i)$ 表示在 $i$ 堆石子时，当前操作的玩家是否有必胜策略。$f(i) = true$ 为必胜，否则必败。
2. 初始时，$f(0) = false$，其余待定。
3. 转移时，对于一个 $i$，枚举 $j$ 满足 $j^2 \le i$。如果存在 $j$ 使得 $f(i - j^2)$ 是必败的，则 $f(i) = true$。否则，$f(i) = false$。
4. 最终答案为 $f(n)$。

时间复杂度

• 状态数为 $O(n)$，转移需要 $O(\sqrt{n})$ 的时间，故总时间复杂度为 $O(n \sqrt{n})$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储状态。

C++ 代码

class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<bool> f(n + 1);
        f[0] = false;

        for (int i = 1; i <= n; i++) {
            f[i] = false;
            for (int j = 1; j * j <= i; j++)
                if (!f[i - j * j]) {
                    f[i] = true;
                    break;
                }
        }

        return f[n];
    }
};