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

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

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

给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。
输入：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）。
'''
class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        if n==0: return False
        if n==1: return True
        if n==2: return False
        dp = [False]*(n+1)
        dp[0] = False
        dp[1] = True
        dp[2] = False
        for i in range(3,n+1):
            j = 1
            while j*j<=i:
            # for j in range(1,math.floor(n**0.5)+1):
                dp[i] =  not dp[i-j*j] 
                if dp[i] == True:
                    break
                j+=1
        # print(dp)
        return dp[n]