Alice and Bob take turns playing a game, with Alice starting first. Initially, there are`n`

stones in a pile. On each player's turn, that player makes amoveconsisting of removinganynon-zerosquare numberof stones in the pile. Also, if a player cannot make a move, he/she loses the game. Given a positive integer`n`

. Return`True`

if and only if Alice wins the game otherwise return`False`

, assuming both players play optimally.

Example 1:Input:n = 1Output:trueExplanation:Alice can remove 1 stone winning the game because Bob doesn't have any moves.Example 2:Input:n = 2Output:falseExplanation:Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).Constraints:`1 <= n <= 10^5`

To solve this problem given `n`

, we need to ‘follow’ the game rules and make decisions. It’s not hard to find out that the subproblems for `n`

– `n'`

that are smaller than n – are needed again and again, so dynamic programming might work here.

#### Dynamic programming

We can initiate an array `dp[]`

such that `dp[i]`

indicates Alice winning/losing when Alice move stones with `n`

equals to `i`

. It’s natural that `dp[1]=1`

. Then for `j`

in `[1...i]`

, if `i-j`

is a square number and `dp[j]==0`

: `dp[i]=1`

. Note that `dp[j]==0`

means Alice will lose when she moves, but it also means Bob will lose since Alice is moving now and the next is Bob.

```
class Solution:
def winnerSquareGame(self, n: int) -> bool:
# 1: Alice wins
# 0: Alice loses
dp = [0]*(n+1) # Alice starts
dp[1] = 1
for i in range(1,n+1):
for j in range(1,int(i**0.5)+1):
if dp[i-j**2] == 0:
dp[i] = 1
break
return dp[-1]
```

#### Optimisation

If we reverse the previous solution, it could achieve O(n). Similarly, we have `dp[]`

but for each `i`

, we could make `dp[j]==1 if dp[i]==0`

and `j-i`

is a square number.

```
class Solution:
def winnerSquareGame(self, n: int) -> bool:
dp = [0]*(n+1) # Alice starts
sq = [i*i for i in range(1, int(n**0.5)+1)]
for i in range(n+1):
if dp[i] == 0:
for j in sq:
if i + j <= n:
dp[i+j] = 1
else:
break
return dp[-1]
```