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 a move consisting of removing any non-zero square number of 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 = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.
Example 2:
Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).
Example 3:
Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Example 4:
Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). 
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).
Example 5:
Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.

 
Constraints:

1 <= n <= 10^5

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Game theory

Mathematics

Starter code: class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        

Solutions:
import math

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp: List[int] = [0] * (n + 1)
		candidates: List[int] = []
		for j in range(1, int(math.sqrt(n)) + 1):
			candidates.append(j * j)
		for i in range(n):
			if not dp[i]:
				for can in candidates:
					if i + can < n:
						dp[i + can] = 1
					elif i + can == n:
						return 1
		return dp[-1]


import math

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def canWin(n):
			bound = math.floor(math.sqrt(n))
			if bound * bound == n:
				return True
			for i in range(bound, 0, -1):
				if not canWin(n - i * i):
					return True
			return False
		return canWin(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(n + 1):
			if dp[i]:
				continue
			for k in range(1, int(n ** 0.5) + 1):
				if i + k * k <= n:
					dp[i + k * k] = True
				else:
					break
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		table = [False] * (n + 1)
		for index in range(n + 1):
			table[index] = any((not table[index - lose * lose] for lose in range(1, 1 + math.floor(math.sqrt(index)))))
		return table[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (max(n, 2) + 1)
		dp[0] = False
		dp[1] = True
		dp[2] = False
		squares = [i ** 2 for i in range(1, floor(sqrt(n)) + 1)]
		for i in range(3, n + 1):
			for square in squares:
				if i - square < 0:
					break
				if dp[i - square] == False:
					dp[i] = True
					break
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		if n == 1:
			return True
		if n == 2:
			return False
		dp = [0] * n
		dp[0] = True
		dp[1] = False
		count = 2
		for i in range(2, n):
			if i + 1 == count ** 2:
				dp[i] = True
				count += 1
			elif dp[i - 1] == False:
				dp[i] = True
			else:
				cur = 0
				for j in range(count - 1, 1, -1):
					if dp[i - j ** 2] == False:
						dp[i] = True
						cur = 1
						break
				if cur == 0:
					dp[i] = False
		return dp[n - 1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		wins = [False] * (n + 1)
		for i in range(1, n + 1):
			j = 1
			canWin = False
			while j * j <= i and (not canWin):
				canWin = not wins[i - j * j]
				j += 1
			wins[i] = canWin
		return wins[n]


import math

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False for i in range(n + 1)]
		dp[0] = True
		dp[1] = True
		for i in range(3, n + 1):
			if math.sqrt(i) == int(math.sqrt(i)):
				dp[i] = True
				continue
			start = 1
			while start * start < i:
				if not dp[i - start * start]:
					dp[i] = True
					break
				start += 1
		print(dp)
		return dp[n]


import math

class Solution:
	squares = []
	dp = {}

	def util(self, n):
		if n == 0:
			return False
		if n in self.dp:
			return self.dp[n]
		for i in range(1, int(math.sqrt(n)) + 1):
			if not self.util(n - self.squares[i]):
				self.dp[n] = True
				return True
		self.dp[n] = False
		return False

	def winnerSquareGame(self, n: int) -> bool:
		self.squares = []
		for i in range(int(math.sqrt(n)) + 1):
			self.squares.append(i * i)
		return self.util(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		if n == 1 or n == 3 or n == 4 or (n == 6):
			return True
		if n == 0 or n == 2 or n == 5:
			return False
		dp = [0, 1, 0, 1, 1, 0, 1, 0]
		i = 8
		while i <= n:
			j = 1
			add = False
			while j * j <= i:
				if dp[i - j * j] == 0:
					dp.append(1)
					add = True
					break
				j += 1
			if not add:
				dp.append(0)
			i += 1
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [0 for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, i + 1):
				if j * j > i:
					break
				if dp[i - j * j] == 0:
					dp[i] = 1
					break
		return dp[-1]


class Solution:

	@lru_cache(None)
	def winnerSquareGame(self, n: int) -> bool:
		if n == 0:
			return False
		if n == 1:
			return True
		xsqrt = int(n ** 0.5)
		for i in range(xsqrt, 0, -1):
			if not self.winnerSquareGame(n - i * i):
				return True
		return False


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		(dp, sqs) = ([False] * (n + 1), [])
		i = 1
		while i * i <= n:
			sqs.append(i * i)
			i += 1
		for i in range(1, n + 1):
			for sq in sqs:
				if sq > i:
					break
				dp[i] = dp[i] or not dp[i - sq]
				if dp[i]:
					break
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			k = 1
			while k * k <= i:
				if dp[i - k * k] == False:
					dp[i] = True
					break
				k += 1
		return dp[n]


from functools import lru_cache

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(maxsize=None)
		def win(cur):
			if cur == 0:
				return False
			for i in range(1, int(cur ** 0.5) + 1):
				if not win(cur - i * i):
					return True
			return False
		return win(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * 160000
		m = 400
		for i in range(1, m):
			dp[i * i] = True
		for i in range(1, n + 1):
			for j in range(1, m):
				if i > j * j:
					if not dp[i - j * j]:
						dp[i] = True
						break
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		squares = [i ** 2 for i in range(1, int(sqrt(n)) + 1)]
		A = [False for _ in range(n + 1)]
		for i in range(1, n + 1):
			if i in squares:
				A[i] = True
				continue
			for square in squares:
				if square > i:
					break
				if not A[i - square]:
					A[i] = True
					break
		return A[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(maxsize=None)
		def dfs(remain):
			if remain == 0:
				return False
			sqrt_root = int(remain ** 0.5)
			for i in range(1, sqrt_root + 1):
				if not dfs(remain - i * i):
					return True
			return False
		return dfs(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		arr = [0] * (n + 1)
		arr[0] = False
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				square = j * j
				if square > i:
					break
				elif square == i:
					arr[i] = True
					break
				else:
					rest = i - square
					if arr[rest] == False:
						arr[i] = True
						break
		return arr[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(maxsize=None)
		def dfs(n):
			if n == 0:
				return False
			square_root = int(sqrt(n))
			for i in range(1, square_root + 1):
				if not dfs(n - i * i):
					return True
			return False
		return dfs(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		mem = [None] * (n + 1)

		def dp(k):
			if k == 0:
				return -1
			if mem[k] != None:
				return mem[k]
			for i in range(int(math.sqrt(k)), 0, -1):
				if dp(k - i * i) < 0:
					mem[k] = 1
					return 1
			mem[k] = -1
			return -1
		return dp(n) > 0


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(maxsize=None)
		def helper(i):
			if i == 0:
				return False
			sr = int(i ** 0.5)
			for k in range(1, sr + 1):
				if not helper(i - k * k):
					return True
			return False
		return helper(n)


import functools

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@functools.lru_cache(maxsize=None)
		def dfs(remaining: int) -> bool:
			if remaining == 0:
				return False
			else:
				sqroot: int = int(remaining ** 0.5)
				for i in range(1, sqroot + 1):
					if dfs(remaining - i * i):
						continue
					else:
						return True
				return False
		return dfs(n)


from collections import deque

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		dp[1] = True
		for x in range(2, n + 1):
			i = 1
			while i * i <= x:
				if not dp[x - i * i]:
					dp[x] = True
					break
				i += 1
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in reversed(range(n)):
			temp = 1
			while i + temp * temp <= n:
				j = i + temp * temp
				temp += 1
				if not dp[j]:
					dp[i] = True
					break
		return dp[0]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			dp[i] = not all((dp[i - k * k] for k in range(1, int(i ** 0.5) + 1)))
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			for j in range(1, int(i ** 0.5) + 1):
				if not dp[i - j * j]:
					dp[i] = True
					break
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(maxsize=None)
		def dfs(remain):
			sqrts = int(sqrt(remain))
			if sqrts ** 2 == remain:
				return True
			for i in range(1, sqrts + 1):
				if not dfs(remain - i * i):
					return True
			return False
		return dfs(n)


def is_winning(n):
	winning = []
	for val in range(0, n + 1):
		if val == 0:
			ans = False
		else:
			ans = False
			i = 1
			while val - i * i >= 0:
				if not winning[val - i * i]:
					ans = True
					break
				i += 1
		winning.append(ans)
	return winning[n]

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		return is_winning(n)


import functools

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@functools.lru_cache(None)
		def can_force_win_from(m):
			if m == 0:
				return False
			if m == 1:
				return True
			for root in range(1, int(m ** 0.5) + 1):
				if not can_force_win_from(m - root * root):
					return True
			return False
		return can_force_win_from(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False for _ in range(n + 1)]
		dp[1] = True
		for i in range(2, n + 1):
			k = 1
			while k * k <= i and (not dp[i]):
				dp[i] = not dp[i - k * k]
				k += 1
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		def is_square(num):
			a = int(num ** 0.5)
			return a * a == num
		dp = [False] * (n + 1)
		dp[0] = False
		dp[1] = True
		for i in range(2, n + 1):
			dp[i] = False
			if is_square(i):
				dp[i] = True
				continue
			limit = int(i ** 0.5)
			for j in range(1, limit + 1):
				if dp[i - j * j] == False:
					dp[i] = True
					break
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		alice = [False] * (n + 1)
		bob = [False] * (n + 1)
		for i in range(1, n + 1):
			for x in range(1, int(sqrt(i)) + 1):
				if not bob[i - x * x]:
					alice[i] = True
					break
			for x in range(1, int(sqrt(i)) + 1):
				if not alice[i - x * x]:
					bob[i] = True
					break
		return alice[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		res = [0] * (n + 1)
		res[1] = 1
		for i in range(2, n + 1):
			for j in range(1, int(math.sqrt(i)) + 1):
				if not res[i - j * j]:
					res[i] = 1
					break
		print(res)
		return res[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def dfs(idx):
			if idx == 0:
				return False
			for i in range(1, int(math.sqrt(idx)) + 1):
				if dfs(idx - i * i) == False:
					return True
			return False
		return dfs(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		wins = [False for i in range(n + 1)]
		wins[1] = True
		for i in range(2, n + 1):
			j = 1
			while i - j * j >= 0:
				if wins[i - j * j] == False:
					wins[i] = True
					break
				j += 1
		return wins[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False for i in range(n + 1)]
		for num in range(1, n + 1):
			for j in range(1, num + 1):
				if j * j > num:
					break
				dp[num] = dp[num] or not dp[num - j * j]
				if dp[num]:
					break
		print(dp)
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False for _ in range(n + 1)]
		for i in range(1, n + 1):
			base = 1
			while i - base ** 2 >= 0:
				if not dp[i - base ** 2]:
					dp[i] = True
					break
				else:
					base += 1
			if i < n and (n - i) ** 0.5 % 1 == 0 and (not dp[i]):
				return True
		return dp[n]


import math

class Solution:

	@lru_cache(None)
	def winnerSquareGame(self, n: int) -> bool:
		if n == 0:
			return False
		i = int(math.sqrt(n))
		while i >= 1:
			if self.winnerSquareGame(n - i * i) == False:
				return True
			i -= 1
		return False


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		res = [False] * (n + 1)
		for i in range(1, n + 1):
			j = 1
			while j * j <= i:
				res[i] |= not res[i - j * j]
				if res[i]:
					break
				j += 1
		return res[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		from functools import lru_cache

		@lru_cache(None)
		def dp(i):
			if i == 0:
				return False
			if i == 1:
				return True
			for k in range(1, i + 1):
				if k * k <= i:
					if not dp(i - k * k):
						return True
				else:
					break
			return False
		return dp(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def dfs(n: int) -> bool:
			if n == 0:
				return False
			if n == 1:
				return True
			k = 1
			while k * k <= n:
				if not dfs(n - k * k):
					return True
				k += 1
			return False
		return dfs(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def win(n):
			if n == 1:
				return True
			if n == 0:
				return False
			v = 1
			while v * v <= n:
				if not win(n - v * v):
					return True
				v += 1
			return False
		return win(n)


from functools import lru_cache

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def dp(m):
			if m == 0:
				return True
			if int(math.sqrt(m)) ** 2 == m:
				return True
			i = 1
			while i * i <= m:
				if not dp(m - i * i):
					return True
				i += 1
			return False
		return dp(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def helper(n):
			if n == 0:
				return 0
			i = 1
			sq = 1
			while sq <= n:
				if helper(n - sq) == 0:
					return 1
				i += 1
				sq = i * i
			return 0
		return helper(n)


import math

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		i = 1
		for i in range(1, n + 1):
			dp[i] = not all((dp[i - j * j] for j in range(1, int(math.sqrt(i)) + 1)))
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False for _ in range(n + 1)]
		for i in range(1, n + 1):
			for e in range(1, int(i ** 0.5) + 1):
				if not dp[i - e ** 2]:
					dp[i] = True
					break
		return dp[-1]


from math import floor, sqrt

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [0 for _ in range(n + 1)]
		for i in range(1, floor(sqrt(n)) + 1):
			dp[i * i] = 1
			great = 1
		for i in range(2, n + 1):
			if dp[i] == 0:
				for j in range(1, great + 1):
					res = (dp[j * j] + dp[i - j * j]) % 2
					if res == 1:
						dp[i] = 1
						break
			else:
				great += 1
		print(dp)
		return True if dp[n] else False


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		losers = {0}
		for x in range(1, n + 1):
			flag = True
			for y in range(1, int(x ** 0.5) + 1):
				if x - y ** 2 in losers:
					flag = False
					break
			if flag:
				losers.add(x)
		return False if n in losers else True


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False]
		for i in range(1, n + 1):
			for b in range(1, math.floor(math.sqrt(i)) + 1):
				if not dp[i - b ** 2]:
					dp.append(True)
					break
			else:
				dp.append(False)
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		sqrs = []
		for j in range(1, n + 1):
			if j * j <= n:
				sqrs.append(j * j)
			else:
				break
		dp = [False] * (1 + n)
		for s in sqrs:
			dp[s] = True
		for i in range(1, n + 1):
			if dp[i]:
				continue
			for s in sqrs:
				if s > i:
					break
				dp[i] = not dp[i - s]
				if dp[i]:
					break
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		dp[1] = True
		for i in range(2, n + 1):
			j = 1
			flag = False
			while j * j <= i:
				if not dp[i - j * j]:
					flag = True
					break
				j += 1
			dp[i] = flag
		return dp[-1]


import math

class Solution:
	cache = {}

	def winnerSquareGame(self, n: int) -> bool:
		if n in self.cache:
			return self.cache[n]
		for i in range(1, int(math.sqrt(n)) + 1):
			if n - i * i == 0:
				self.cache[n] = True
				return True
			if not self.winnerSquareGame(n - i * i):
				self.cache[n] = True
				return True
		self.cache[n] = False
		return False


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [None] * (n + 1)
		squares = []
		for i in range(1, n + 1):
			if i ** 2 > n:
				break
			squares.append(i ** 2)
			dp[i ** 2] = True
		for i in range(1, n + 1):
			if dp[i] is not None:
				continue
			cur = True
			for s in squares:
				if s > i:
					break
				cur = cur and dp[i - s]
			dp[i] = not cur
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		l = [1]
		pos = [0] * (n + 1)
		for i in range(1, n + 1):
			if i == (math.sqrt(l[-1]) + 1) ** 2:
				l.append(int((math.sqrt(l[-1]) + 1) ** 2))
			for square_num in l:
				if not pos[i - square_num]:
					pos[i] = 1
		return pos[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		mem = {}
		squares = []
		if int(pow(n, 0.5)) == pow(n, 0.5):
			return True

		def helper(n):
			if n in mem:
				return mem[n]
			for i in range(1, int(pow(n, 0.5)) + 1):
				if not helper(n - i * i):
					mem[n] = True
					return True
			mem[n] = False
			return False
		return helper(n)

	def calcSquares(self, mem, squares, n):
		for i in range(1, n):
			i = pow(i, 0.5)
			if int(i) == i:
				squares.append(i)
				mem[i] = True


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		res = [False] * (n + 1)
		for i in range(n + 1):
			if res[i]:
				continue
			j = 1
			while i + j * j <= n:
				res[i + j * j] = True
				j += 1
		return res[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		s = [i ** 2 for i in range(1, int(n ** (1 / 2)) + 1)]
		record = {}

		def helper(i):
			if i in record:
				return record[i]
			if i == 0:
				return False
			for j in s:
				if j > i:
					record[i] = False
					return False
				if not helper(i - j):
					record[i] = True
					return True
		res = helper(n)
		return res


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		sol = [False] * (n + 1)
		for i in range(1, n + 1):
			j = pwr = 1
			sol[i] = False
			while pwr <= i:
				if not sol[i - pwr]:
					sol[i] = True
					break
				j += 1
				pwr = j ** 2
		return sol[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		ans = [False] * (n + 1)
		for i in range(1, n + 1):
			ans[i] = not all((ans[i - j ** 2] for j in range(1, 1 + int(i ** 0.5))))
		return ans[-1]


class Solution:

	def winnerSquareGame2(self, n):
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			dp[i] = not all((dp[i - k * k] for k in range(1, int(i ** 0.5) + 1)))
		return dp[-1]

	def winnerSquareGame(self, n: int) -> bool:
		cache = dict()

		def solve(s):
			if s in cache:
				return cache[s]
			if s == 0:
				cache[s] = False
				return False
			if pow(int(sqrt(s)), 2) == s:
				cache[s] = True
				return True
			iswin = False
			for k in range(1, int(sqrt(s)) + 1):
				if not solve(s - k * k):
					iswin = True
					break
			cache[s] = iswin
			return iswin
		return solve(n)


def canWin(n, squares, memo):
	if n in squares:
		return True
	if n in memo:
		return memo[n]
	res = False
	for i in reversed(squares):
		if i > n:
			continue
		if not canWin(n - i, squares, memo):
			res = True
			break
	memo[n] = res
	return res

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		squares = [i ** 2 for i in range(1, floor(sqrt(n)) + 1)]
		memo = dict()
		return canWin(n, squares, memo)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		return self.dfs(n)

	@lru_cache(None)
	def dfs(self, remain):
		sqrt_root = int(math.sqrt(remain))
		for i in range(1, sqrt_root + 1):
			if not self.dfs(remain - i * i):
				return True
		return False


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		def dp_search(dp, n):
			if n == 0:
				return False
			if n == 1:
				return True
			if n in dp:
				return dp[n]
			dp[n] = False
			i = int(sqrt(n))
			while i >= 1:
				if dp_search(dp, n - i * i) == False:
					dp[n] = True
					return True
				i -= 1
			return False
		dp = {}
		return dp_search(dp, n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			dp[i] = any((not dp[i - j ** 2] for j in range(1, int(i ** 0.5) + 1)))
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		choices = [1]
		memo = {}
		for i in range(2, n):
			if i * i > n:
				break
			choices.append(i * i)

		def find(n):
			if n == 0:
				return False
			if n in memo:
				return memo[n]
			for i in choices:
				if i > n:
					break
				if not find(n - i):
					memo[n] = True
					return True
			memo[n] = False
			return False
		return find(n)


class Solution:

	@lru_cache(None)
	def winnerSquareGame(self, n: int) -> bool:
		for i in range(1, int(sqrt(n)) + 1):
			if not self.winnerSquareGame(n - i * i):
				return True
		return False


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		memo = {0: False}

		def dp(i):
			if i in memo:
				return memo[i]
			m = int(i ** 0.5)
			if i ** 0.5 == m:
				return True
			res = False
			for j in range(1, m + 1):
				res |= not dp(i - j * j)
				if res:
					memo[i] = True
					return True
			memo[i] = False
			return False
		return dp(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		mem = {}

		def game(n):
			if n in mem:
				return mem[n]
			if n == 0:
				return False
			k = 1
			mem[n] = False
			while k * k <= n:
				if not game(n - k * k):
					mem[n] = True
					break
				k += 1
			return mem[n]
		game(n)
		return mem[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		cost = [-1 for _ in range(n + 1)]

		@lru_cache(None)
		def helper(n):
			if n == 0:
				return 0
			if cost[n] != -1:
				return cost[n]
			i = 1
			sq = 1
			while sq <= n:
				if cost[n - sq] != -1:
					return cost[n - sq]
				if helper(n - sq) == 0:
					cost[n - sq] = 1
					return 1
				i += 1
				sq = i * i
			cost[n] = 0
			return 0
		return helper(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def win(amt):
			x = int(math.sqrt(amt))
			for i in range(x, 0, -1):
				if not win(amt - i * i):
					return True
			return False
		return win(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		self.memo = dict()
		return self.dfs(n)

	def dfs(self, stonesRemain):
		if stonesRemain <= 0:
			return False
		if stonesRemain in self.memo:
			return self.memo[stonesRemain]
		squareRoot = int(stonesRemain ** 0.5)
		res = False
		for i in reversed(range(1, squareRoot + 1)):
			if not self.dfs(stonesRemain - i * i):
				res = True
				break
		self.memo[stonesRemain] = res
		return res


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		x = 1
		s = []
		st = set()
		dp = [False] * (n + 1)
		while x * x <= n:
			s.append(x * x)
			st.add(x * x)
			dp[x * x] = True
			x += 1
		if n in s:
			return True
		for i in range(1, n + 1):
			if dp[i] == False:
				start = 0
				while start < len(s) and i - s[start] > 0:
					if dp[i - s[start]] == False:
						dp[i] = True
						break
					start += 1
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		cache = {}

		def helper(n):
			if n in cache:
				return cache[n]
			s = sqrt(n)
			if s.is_integer():
				cache[n] = True
				return True
			i = 1
			while i < s:
				j = i * i
				if not helper(n - j):
					cache[n] = True
					return True
				i += 1
			cache[n] = False
			return False
		return helper(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		dp[1] = True
		for i in range(2, n + 1):
			dp[i] = not all((dp[i - j * j] for j in range(1, int(math.sqrt(i)) + 1) if i >= j * j))
		return dp[-1]


import math
from collections import defaultdict

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		def dfs(position, player):
			if position in cache:
				if cache[position] == True:
					return player
				return not player
			for sq in squares:
				if sq == position:
					cache[position] = player
					return player
				if sq > position:
					break
				if player == dfs(position - sq, not player):
					cache[position] = player
					return player
			cache[position] = not player
			return not player
		cache = defaultdict(bool)
		max_val = int(math.sqrt(n))
		squares = [1]
		for i in range(2, max_val + 1):
			squares.append(i ** 2)
		cache[1] = True
		cache[2] = False
		cache[3] = True
		cache[4] = True
		for i in range(5, n + 1):
			cache[i] = dfs(i, True)
		return cache[n]


import math

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False for _ in range(n + 1)]
		dp[1] = True
		for i in range(2, n + 1):
			sqr = int(i ** 0.5)
			for j in range(1, sqr + 1):
				dp[i] |= not dp[i - j ** 2]
				if dp[i]:
					break
		return dp[n]


import math

class Solution:

	def helper(self, n: int, dp: dict) -> bool:
		if n in dp:
			return dp[n]
		if n == 0:
			return False
		i = 1
		while i * i <= n:
			if self.helper(n - i * i, dp) == False:
				dp[n] = True
				return True
			i += 1
		dp[n] = False
		return False

	def winnerSquareGame(self, n: int) -> bool:
		dp = {}
		return self.helper(n, dp)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		if n == 1:
			return True
		dp = [0, 1]
		for i in range(2, n + 1):
			root = int(i ** 0.5)
			if root ** 2 == i:
				dp.append(1)
			else:
				for j in range(1, root + 1):
					if not dp[i - j ** 2]:
						dp.append(1)
						break
			if len(dp) == i:
				dp.append(0)
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		if n == 0 or n == 2:
			return False
		if n == 1:
			return True
		dp = [-1] * (n + 1)
		dp[0] = 0
		dp[1] = 1
		dp[2] = 0

		def pick(n):
			if dp[n] != -1:
				return dp[n]
			i = 1
			while i * i <= n:
				if i * i == n:
					dp[n] = 1
					return True
				if not pick(n - i * i):
					dp[n] = 1
					return True
				i = i + 1
			dp[n] = 0
			return dp[n]
		pick(n)
		return dp[n] == 1


import math

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		return self.alice_wins(n, {})

	def alice_wins(self, n, dp):
		if n in dp:
			return dp[n]
		x = 1
		dp[n] = False
		while x * x <= n:
			if not self.alice_wins(n - x * x, dp):
				dp[n] = True
				break
			x += 1
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		memo = {}

		def helper(n):
			if n in memo:
				return memo[n]
			if n == 0:
				return False
			if n == 1:
				return True
			i = 1
			while i * i <= n:
				win = helper(n - i * i)
				if not win:
					memo[n] = True
					return True
				i += 1
			memo[n] = False
			return False
		res = helper(n)
		return res


from functools import lru_cache

class Solution:

	@lru_cache(None)
	def dp(self, n):
		if n == 0:
			return False
		for s in self.s:
			if n - s >= 0:
				if not self.dp(n - s):
					return True
		return False

	def winnerSquareGame(self, n: int) -> bool:
		(self.s, i) = ([1], 1)
		while self.s[-1] < 10 ** 5:
			i += 1
			self.s.append(i * i)
		return self.dp(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			if i ** 0.5 == int(i ** 0.5):
				dp[i] = 1
				continue
			else:
				for j in range(1, int(i ** 0.5) + 1):
					if dp[i - j ** 2] == 0:
						dp[i] = 1
						break
		return bool(dp[n])


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		mem = {}

		def get_dp(i):
			if i == 0:
				return False
			elif i not in mem:
				root = 1
				while True:
					if root * root > i:
						mem[i] = False
						break
					else:
						if not get_dp(i - root * root):
							mem[i] = True
							break
						root += 1
			return mem[i]
		return get_dp(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		roots = [i * i for i in range(1, int(sqrt(n)) + 1)]
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			for j in roots:
				if i < j:
					break
				if not dp[i - j]:
					dp[i] = True
		return dp[n]


from functools import lru_cache

class Solution:

	@lru_cache(None)
	def winnerSquareGame(self, n: int) -> bool:
		if n == 0:
			return False
		x = 1
		while x * x <= n:
			if not self.winnerSquareGame(n - x * x):
				return True
			x += 1
		return False


import functools
from math import sqrt

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@functools.lru_cache(maxsize=10 ** 5)
		def WSG(k):
			if k == 0:
				return False
			i = int(sqrt(k))
			while i >= 1:
				if not WSG(k - i ** 2):
					return True
				i -= 1
			return False
		return WSG(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		memo = {}

		def isSquare(n):
			root = int(n ** 0.5)
			return root * root == n

		def dfs(n):
			if n in memo:
				return memo[n]
			if isSquare(n):
				memo[n] = True
				return memo[n]
			root = int(n ** 0.5)
			memo[n] = False
			for i in range(1, root + 1):
				if not dfs(n - i * i):
					memo[n] = True
					break
			return memo[n]
		return dfs(n)


class Solution:

	def stone_game(self, memo, n):
		if n in memo:
			return memo[n]
		memo[n] = False
		for cand in range(1, int(math.sqrt(n)) + 1):
			i = cand * cand
			memo[n] = memo[n] or not self.stone_game(memo, n - i)
			if memo[n]:
				return True
		return memo[n]

	def winnerSquareGame(self, n: int) -> bool:
		can_i_win = defaultdict(bool)
		can_i_win[1] = True
		can_i_win[0] = False
		self.stone_game(can_i_win, n)
		return can_i_win[n]


class Solution:

	@lru_cache(None)
	def winnerSquareGame(self, n: int) -> bool:
		if n == 1:
			return True
		s = 1
		while s * s <= n:
			flag = self.winnerSquareGame(n - s * s)
			if flag == False:
				return True
			s += 1
		return False


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		winmap = {}
		winmap[0] = False
		winmap[1] = True

		def fill_map(n):
			if n in winmap:
				return winmap[n]
			i = 1
			winmap[n] = 0
			while i * i <= n:
				winmap[n] = winmap[n] or not fill_map(n - i * i)
				if winmap[n]:
					break
				i += 1
			return winmap[n]
		for i in range(1, n):
			fill_map(n)
		return winmap[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		memo = {0: False}

		def dfs(i):
			if i not in memo:
				memo[i] = False
				j = 1
				while not memo[i] and j * j <= i:
					memo[i] = not dfs(i - j * j)
					j += 1
			return memo[i]
		return dfs(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		squares = [i * i for i in range(1, int(n ** 0.5) + 1)]
		DP = [0] * (1 + n)
		for i in range(1, n + 1):
			can_win = False
			for s in squares:
				if s > i:
					break
				can_win |= not DP[i - s]
			DP[i] = can_win
		return DP[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		dp[1] = True
		for i in range(2, n + 1):
			for k in range(1, int(i ** 0.5) + 1):
				if dp[i - k * k] == False:
					dp[i] = True
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			for j in range(1, int(sqrt(i)) + 1):
				if dp[i - j ** 2] is False:
					dp[i] = True
					break
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		m = {0: False, 1: True}

		def helper(n):
			if n in m:
				return m[n]
			(ans, start) = (False, 1)
			while start * start <= n:
				ans = ans or not helper(n - start * start)
				if ans:
					m[n] = ans
					return ans
				start += 1
			m[n] = ans
			return ans
		return helper(n)


class Solution:

	@lru_cache(None)
	@lru_cache(maxsize=None)
	def winnerSquareGame(self, n: int) -> bool:
		if n == 0:
			return False
		else:
			for i in range(1, int(n ** 0.5) + 1):
				if not self.winnerSquareGame(n - i ** 2):
					return True
			return False


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			cur = int(i ** 0.5)
			if cur ** 2 == i:
				dp[i] = True
			else:
				f = True
				for j in range(1, int(i ** 0.5) + 1):
					f &= dp[i - j * j]
				if not f:
					dp[i] = True
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		M = {}
		M[0] = False
		M[1] = True
		for i in range(2, n + 1):
			M[i] = False
			sq = int(math.sqrt(i))
			if sq ** 2 == i:
				M[i] = True
			for j in range(1, sq + 1):
				M[i] = M[i] or not M[i - j * j]
		return M[n]


from functools import lru_cache

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def dp(num):
			sqr = int(num ** (1 / 2))
			if sqr ** 2 == num:
				return True
			way = False
			for i in range(1, sqr + 1):
				way = not dp(num - i ** 2)
				if way:
					return True
			return way
		return dp(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [0] * (n + 1)
		squares = []
		i = 1
		nxt_sqrt = 1
		nxt = 1
		for i in range(1, n + 1):
			if i == nxt:
				dp[i] = 1
				squares.append(nxt)
				nxt_sqrt += 1
				nxt = nxt_sqrt ** 2
			else:
				dp[i] = max((-dp[i - s] for s in squares))
		return dp[n] == 1


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		if n == 0:
			return False
		if n == 1:
			return True
		squares = [i ** 2 for i in range(1, int(sqrt(n)) + 1)]

		@lru_cache(None)
		def dp(i):
			nonlocal squares
			canWin = False
			for sq in squares:
				if i < sq:
					break
				if i == sq:
					return True
				canWin = canWin or not dp(i - sq)
			return canWin
		return dp(n)


import math

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		result = [None] * (n + 1)

		def canWin(n):
			bound = math.ceil(math.sqrt(n))
			if bound * bound == n:
				result[n] = True
				return True
			if result[n] != None:
				return result[n]
			for i in range(1, bound):
				if not canWin(n - i * i):
					result[n] = True
					return True
			result[n] = False
			return False
		return canWin(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def rec(n):
			if n < 2:
				return n == 1
			return any((not rec(n - i * i) for i in range(int(n ** 0.5), 0, -1)))
		return rec(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False]
		for i in range(1, n + 1):
			b = 1
			winnable = False
			while b ** 2 <= i:
				if not dp[i - b ** 2]:
					winnable = True
					break
				b += 1
			dp.append(winnable)
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		cache = {}

		def helper(number):
			if number == 0:
				return False
			if number not in cache:
				flag = False
				for i in range(1, 317):
					val = i ** 2
					if val > number:
						break
					if not helper(number - val):
						flag = True
						break
				cache[number] = flag
			return cache[number]
		return helper(n)


from math import sqrt

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		dp[1] = True
		for m in range(2, n + 1):
			i = 1
			while i ** 2 < m:
				if not dp[m - i ** 2]:
					dp[m] = True
					break
				i += 1
			if i ** 2 == m:
				dp[m] = True
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		table = [False] * (n + 1)
		table[1] = True
		for i in range(2, n + 1):
			num = 1
			while num ** 2 <= i:
				square = num ** 2
				if not table[i - square]:
					table[i] = True
					break
				num += 1
		return table[-1]


class Solution:

	@lru_cache(None)
	def winnerSquareGame(self, n: int) -> bool:
		if n == 1:
			return True
		sqrt = math.floor(math.sqrt(n))
		if sqrt * sqrt == n:
			return True
		for num in range(1, sqrt + 1):
			if not self.winnerSquareGame(n - num ** 2):
				return True
		return False


class Solution:

	@lru_cache(None)
	def winnerSquareGame(self, n: int) -> bool:
		table = [False for x in range(n + 1)]
		for x in range(1, n + 1):
			flag = False
			c = 1
			while c ** 2 <= x:
				if not table[x - c ** 2]:
					flag = True
					break
				c += 1
			table[x] = flag
		return table[-1]


from functools import lru_cache

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		sq = [x * x for x in range(1, 317)]
		dp = [False] * (n + 1)
		for i in range(n + 1):
			for x in sq:
				if i - x < 0:
					break
				if dp[i - x] == False:
					dp[i] = True
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dic = dict()
		dic[1] = True
		dic[2] = False
		dic[3] = True
		dic[4] = True

		def helper(n):
			if n in dic:
				return dic[n]
			i = int(n ** 0.5)
			while i >= 1:
				if not helper(n - i ** 2):
					dic[n] = True
					return True
				i -= 1
			dic[n] = False
			return False
		return helper(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [-1] * (n + 1)
		dp[0] = 0
		return self.can_win(n, dp)

	def can_win(self, n, dp):
		if dp[n] != -1:
			return dp[n]
		root = 1
		cur = n - root ** 2
		while cur >= 0:
			dp[cur] = self.can_win(cur, dp)
			if dp[cur] == 0:
				dp[n] = 1
				return 1
			root += 1
			cur = n - root ** 2
		dp[n] = 0
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		memo = {}

		def f(x):
			if x == 0:
				return False
			if x == 1:
				return True
			if x in memo:
				return memo[x]
			i = 1
			while i * i <= x:
				if f(x - i * i) == False:
					memo[x] = True
					return True
				i += 1
			memo[x] = False
			return False
		return f(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def dp(i):
			if i == 0:
				return False
			return any((not dp(i - x * x) for x in range(floor(sqrt(i)), 0, -1)))
		return dp(n)


import math

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			curr = 1
			while curr ** 2 <= i:
				if dp[i - curr ** 2] == False:
					dp[i] = True
					break
				curr += 1
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			base = 1
			while i - base ** 2 >= 0:
				if dp[i - base ** 2] == False:
					dp[i] = 1
					break
				base += 1
		return dp[-1]


class Solution:

	def __init__(self):
		self.memo = {0: False}

	def winnerSquareGame(self, n: int) -> bool:

		def rwsg(n, picks):
			if n not in self.memo:
				out = False
				for p in picks:
					if p > n:
						break
					out = out or not rwsg(n - p, picks)
				self.memo[n] = out
			return self.memo[n]
		picks = []
		m = 1
		while m * m <= n:
			picks.append(m * m)
			m += 1
		rwsg(n, picks)
		return rwsg(n, picks)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		def removeSquare(n: int, memo: [int]):
			if n == 0:
				return False
			if memo[n]:
				return memo[n]
			i = 1
			while i * i <= n:
				if memo[n - i * i] == False:
					return True
				memo[n - i * i] = removeSquare(n - i * i, memo)
				if memo[n - i * i] == False:
					return True
				i += 1
			return False
		memo = [None] * (n + 1)
		return removeSquare(n, memo)


import functools
import math

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@functools.lru_cache(None)
		def dp(k):
			if k <= 0:
				return False
			sq = math.sqrt(k)
			if sq.is_integer():
				return True
			for m in range(1, k):
				if m ** 2 > k:
					break
				ans = dp(k - m ** 2)
				if not ans:
					return True
			return False
		return dp(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		n2p = []
		p2n = {}
		for x in range(n + 1):
			n2p.append(x ** 2)
			p2n[x ** 2] = x

		@lru_cache(None)
		def recur(rem):
			if rem == 0:
				return False
			if round(math.sqrt(rem)) ** 2 == rem:
				return True
			max_rm_val = math.floor(math.sqrt(rem)) ** 2
			max_rm_ind = p2n[max_rm_val]
			for ind in range(max_rm_ind, 0, -1):
				if not recur(rem - n2p[ind]):
					return True
			return False
		return recur(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		if n == 1:
			return True
		dp = [False] * (n + 1)
		squares = set()
		for i in range(1, n // 2 + 1):
			square = i * i
			if square <= n:
				squares.add(square)
				dp[square] = True
		for i in range(1, n + 1):
			if i not in squares:
				possible = [not dp[i - square] for square in squares if square < i]
				dp[i] = any(possible)
		return dp[-1]


import functools

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@functools.lru_cache(maxsize=None)
		def WSG(k):
			if k == 0:
				return False
			i = 1
			while i ** 2 <= k:
				if not WSG(k - i ** 2):
					return True
				i += 1
			return False
		return WSG(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		squart_num = []
		dp = [False] * (n + 1)
		i = 1
		for i in range(1, n + 1):
			start_index = 1
			while True:
				if start_index * start_index > i:
					break
				if not dp[i - start_index * start_index]:
					dp[i] = True
				start_index += 1
				pass
		if dp[n] == 1:
			return True
		return False
		pass


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		from functools import lru_cache

		@lru_cache(None)
		def can_win(remain):
			if remain == 0:
				return False
			root = 1
			while root ** 2 <= remain:
				if not can_win(remain - root ** 2):
					return True
				root += 1
			return False
		return can_win(n)


class Solution:

	def __init__(self):
		self.isGood = {}

	def winnerSquareGame(self, n: int) -> bool:
		if n <= 0:
			return False
		if n in self.isGood:
			return self.isGood[n]
		self.isGood[n] = False
		i = 1
		while i * i <= n:
			if not self.winnerSquareGame(n - i * i):
				self.isGood[n] = True
				return True
			i += 1
		return self.isGood[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def helper(n):
			if n == 0:
				return -1
			for i in range(int(sqrt(n)), 0, -1):
				if helper(n - i * i) < 0:
					return 1
			return -1
		return helper(n) > 0


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = defaultdict(bool)

		def helper(n):
			if n == 0:
				return False
			if n in dp:
				return dp[n]
			for i in range(1, int(n ** 0.5) + 1):
				if not helper(n - i ** 2):
					dp[n] = True
					return True
			dp[n] = False
			return False
		return helper(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [-1 for i in range(n + 1)]

		def help(n):
			if dp[n] == -1:
				if n < 1:
					result = False
				else:
					result = False
					i = 1
					while i ** 2 <= n:
						move = i ** 2
						result = result or not help(n - move)
						if result:
							break
						i += 1
				dp[n] = result
			return dp[n]
		return help(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		memo = {0: False}

		def wing(x):
			if math.sqrt(x) == int(math.sqrt(x)):
				return True
			if x in memo:
				return memo[x]
			i = 1
			ans = False
			while i * i <= x:
				if wing(x - i * i) == False:
					ans = True
					break
				i += 1
			memo[x] = ans
			return ans
		return wing(n)


class Solution:

	@lru_cache(1024 ** 2)
	def winnerSquareGame(self, n: int) -> bool:
		if n == 0:
			return False
		for i in range(1, int(sqrt(n)) + 1):
			if i * i > n:
				continue
			if not self.winnerSquareGame(n - i * i):
				return True
		return False


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		square = []
		for i in range(1, n + 1):
			if i * i <= n:
				square.append(i * i)
			else:
				break
		from functools import lru_cache

		@lru_cache(None)
		def dp(n, state):
			if n == 0:
				if state == 1:
					return False
				else:
					return True
			if state == 1:
				tmp = False
				for num in square:
					if num <= n:
						tmp = tmp or dp(n - num, 1 - state)
						if tmp == True:
							return tmp
					else:
						break
			else:
				tmp = True
				for num in square:
					if num <= n:
						tmp = tmp and dp(n - num, 1 - state)
						if tmp == False:
							return tmp
					else:
						break
			return tmp
		return dp(n, 1)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(1, len(dp)):
			j = 1
			while j * j <= i:
				if dp[i - j * j] == False:
					dp[i] = True
				j += 1
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [0] * (n + 3)
		dp[1] = 1
		dp[2] = 0
		for i in range(3, n + 1):
			for j in range(1, int(i ** 0.5) + 1):
				if j ** 2 <= i:
					if dp[i - j ** 2] == 0:
						dp[i] = 1
						break
		print(dp[n])
		return dp[n] == 1


class Solution:

	@lru_cache(None)
	def winnerSquareGame(self, n: int) -> bool:
		if n == 0 or n == 1:
			return True
		i = 1
		while i ** 2 < n:
			if not self.winnerSquareGame(n - i ** 2):
				return True
			i += 1
		return i ** 2 == n


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		lookup = {}

		def getSquareNumbers(n: int) -> List[int]:
			if n in lookup:
				return lookup[n]
			lookup[n] = [index * index for index in range(1, 1 + math.floor(math.sqrt(n)))]
			return lookup[n]
		table = [False] * (n + 1)
		for index in range(n + 1):
			table[index] = any((not table[index - lose] for lose in getSquareNumbers(index)))
		return table[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [0, 1]
		for s in range(2, n + 1):
			dp.append(0)
			i = 1
			while i ** 2 <= s:
				dp[-1] = max(dp[-1], 1 - dp[s - i ** 2])
				if dp[-1] == 1:
					break
				i += 1
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			j = 1
			while j * j <= i:
				dp[i] |= not dp[i - j * j]
				j += 1
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def dp(n, people):
			for i in range(1, 400):
				if i * i <= n:
					result = dp(n - i * i, 0 if people is 1 else 1)
					if people == 0:
						if result:
							return result
					elif not result:
						return result
				else:
					break
			if people == 0:
				return False
			else:
				return True
		return dp(n, 0)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def dfs(m, p):
			if m == 0:
				return p == 1
			if m == 1:
				return p == 0
			i = 1
			while i * i <= m:
				if p == 0 and dfs(m - i * i, 1):
					return True
				elif p == 1 and (not dfs(m - i * i, 0)):
					return False
				i += 1
			return p == 1
		return dfs(n, 0)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		win = [False]
		for i in range(n):
			j = 1
			can_win = False
			while j ** 2 <= len(win):
				if not win[-j ** 2]:
					can_win = True
					break
				j += 1
			win.append(can_win)
		return win[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def get(k):
			if not k:
				return False
			return not all([get(k - i * i) for i in range(1, int(k ** 0.5) + 1)])
		return get(n)


class Solution:

	@lru_cache(None)
	def winnerSquareGame(self, n: int) -> bool:
		if n == 0:
			return False
		return any((not self.winnerSquareGame(n - x ** 2) for x in range(int(n ** 0.5), 0, -1)))


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = {0: False}
		for i in range(0, n):
			if i in dp and i != 0:
				continue
			for j in range(1, n + 1):
				if i + j * j > n:
					break
				dp[i + j * j] = True
		return False if n not in dp else dp[n]


import math

class Solution:
	squares = [0]
	dp = [False]

	def winnerSquareGame(self, n: int) -> bool:
		sqt = int(math.sqrt(n))
		for i in range(len(self.squares), sqt + 1):
			self.squares.append(i * i)
		if n + 1 <= len(self.dp):
			return self.dp[n]
		old_len = len(self.dp)
		for i in range(old_len, n + 1):
			self.dp.append(False)
		for i in range(old_len, n + 1):
			flag = 0
			for j in range(1, int(math.sqrt(i)) + 1):
				if not self.dp[i - self.squares[j]]:
					self.dp[i] = True
					flag = 1
					break
			if flag == 0:
				self.dp[i] = False
		return self.dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def dp(n, people):
			for i in range(floor(math.sqrt(n)), 0, -1):
				if i * i <= n:
					result = dp(n - i * i, 0 if people is 1 else 1)
					if people == 0:
						if result:
							return result
					elif not result:
						return result
			if people == 0:
				return False
			else:
				return True
		return dp(n, 0)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		win = [False] * (n + 1)
		for i in range(n):
			if not win[i]:
				j = 1
				while i + j ** 2 <= n:
					if i + j ** 2 == n:
						return True
					win[i + j ** 2] = True
					j += 1
		return False


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		to_ret = [False]
		for i in range(1, n + 1):
			for j in range(int(i ** 0.5), 0, -1):
				if not to_ret[i - j * j]:
					to_ret.append(True)
					break
			if len(to_ret) == i:
				to_ret.append(False)
		return to_ret[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		base = 1
		steps = []
		dp = [False for i in range(n + 1)]
		for i in range(1, n + 1):
			if base * base <= i:
				steps.append(base * base)
				base += 1
			for step in steps:
				if not dp[i - step]:
					dp[i] = True
					break
		return dp[-1]


from functools import lru_cache

class Solution:

	@lru_cache(None)
	def winnerSquareGame(self, n: int) -> bool:
		k = int(math.sqrt(n))
		if k * k == n or n == 3:
			return True
		if n == 2:
			return False
		if all((self.winnerSquareGame(n - i ** 2) for i in range(k, 0, -1))):
			return False
		return True


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		def dfs(n):
			if n == 0:
				return False
			if int(n ** 0.5) ** 2 == n:
				return True
			if n not in dic:
				dic[n] = any((not dfs(n - i) for i in poss if i <= n))
			return dic[n]
		poss = []
		dic = {}
		for i in range(1, int(n ** 0.5) + 1):
			poss.append(i * i)
		poss = poss[::-1]
		return dfs(n)


from math import sqrt

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		from functools import lru_cache

		@lru_cache(None)
		def df(x):
			if int(sqrt(x)) ** 2 == x:
				return True
			if not x:
				return False
			for i in range(int(sqrt(x)), 0, -1):
				if not df(x - i * i):
					return True
			return False
		return df(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		self.sqnums = [x ** 2 for x in range(1, 317)]
		self.cache = dict(((sn, True) for sn in self.sqnums))

		def dp(n):
			if n in self.cache:
				return self.cache[n]
			x = int(sqrt(n))
			while x > 0:
				sn = self.sqnums[x - 1]
				if sn >= n:
					break
				if not dp(n - sn):
					self.cache[n] = True
					return True
				x -= 1
			return False
		return dp(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		s = [i ** 2 for i in range(1, int(n ** (1 / 2)) + 1)]
		dp = [0 for i in range(n + 1)]
		(dp[0], dp[1]) = (False, True)
		for i in range(2, n + 1):
			for j in s:
				if j > i:
					dp[i] = False
					break
				if dp[i - j] == False:
					dp[i] = True
					break
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			for base in range(1, int(math.sqrt(i)) + 1):
				take = base * base
				if not dp[i - take]:
					dp[i] = True
					break
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def dfs(stones):
			if stones <= 0:
				return False
			for i in reversed(list(range(1, int(sqrt(stones)) + 1))):
				square = i * i
				if stones - square == 0 or not dfs(stones - square):
					return True
			return False
		return dfs(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False for i in range(n + 1)]
		sqs = [i * i for i in range(1, 1 + int(math.sqrt(n)))]
		for i in range(n + 1):
			t = False
			for sq in sqs:
				if i - sq < 0:
					break
				if not dp[i - sq]:
					t = True
					break
			dp[i] = t
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def helper(i):
			if i == 0:
				return False
			base = int(i ** 0.5)
			return any((not helper(i - j * j) for j in range(base, 0, -1)))
		return helper(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		if int(n ** 0.5) ** 2 == n:
			return True
		sqdict = {i * i: 1 for i in range(1, n + 1)}
		dp = [False for i in range(n + 1)]
		dp[:4] = [False, True, False, True]
		for i in range(4, n + 1):
			if sqdict.get(i, 0) == 1:
				dp[i] = True
			else:
				for j in sqdict:
					if j > i:
						break
					if dp[i - j] == False:
						dp[i] = True
						break
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		if n == 1:
			return True
		dp = [None] * (n + 1)
		(dp[0], dp[1], dp[2]) = (False, True, False)
		for i in range(3, n + 1):
			for j in range(1, n * n):
				y = i - j * j
				if y < 0:
					break
				if not dp[y]:
					dp[i] = True
					break
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [False, True, False]
		for x in range(3, n + 1):
			dp.append(False)
			for y in range(1, n):
				a = x - y * y
				if a < 0:
					break
				if not dp[a]:
					dp[x] = True
					break
		return dp[n]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		DP = [0] * (1 + n)
		for i in range(1, n + 1):
			DP[i] = not all((DP[i - j * j] for j in range(1, int(i ** 0.5) + 1)))
		return DP[-1]


class Solution:

	def findWinner(self, res, sqlist, n, t, turn):
		if turn == 'Alice':
			if res[t] == 1:
				res[n] = 1
				return res
			if res[t] == 2:
				return res
			if res[t] == 0:
				ind = len(sqlist) - 1
				while ind >= 0:
					temp = t - sqlist[ind]
					if temp >= 0:
						fw1 = Solution()
						res = fw1.findWinner(res, sqlist, n, temp, 'Bob')
						if res[temp] == 2:
							res[t] = 1
							res[n] = 1
							return res
					ind -= 1
				res[t] = 2
				return res
		if turn == 'Bob':
			if res[t] == 2:
				res[n] = 1
				return res
			if res[t] == 1:
				return res
			if res[t] == 0:
				ind = len(sqlist) - 1
				while ind >= 0:
					temp = t - sqlist[ind]
					if temp >= 0:
						fw2 = Solution()
						res = fw2.findWinner(res, sqlist, n, temp, 'Alice')
						if res[temp] == 2:
							res[t] = 1
							res[n] = 2
							return res
					ind -= 1
				res[t] = 2
				return res
		return res

	def winnerSquareGame(self, n: int) -> bool:
		if n == 0:
			return False
		res = []
		for i in range(n + 1):
			res.append(0)
		sqlist = []
		i = 1
		isq = 1
		while isq <= n:
			sqlist.append(isq)
			res[isq] = 1
			i += 1
			isq = i ** 2
		fw = Solution()
		finres = fw.findWinner(res, sqlist, n, n, 'Alice')
		if finres[n] == 1:
			return True
		else:
			return False


from functools import lru_cache

class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		@lru_cache(None)
		def dp(i):
			sq = int(math.sqrt(i))
			if sq ** 2 == i:
				return True
			ans = False
			for m in [n ** 2 for n in range(1, sq + 1)][::-1]:
				ans = ans or not dp(i - m)
				if ans:
					return True
			return ans
		return dp(n)


class Solution:

	def winnerSquareGame(self, n: int) -> bool:

		def is_square(n):
			root = math.sqrt(i)
			return root == int(root)
		dp = [False] * (n + 1)
		squares = []
		for i in range(1, n + 1):
			if is_square(i):
				squares.append(i)
			dp[i] = any((not dp[i - square] for square in squares))
		return dp[-1]


class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		result = []
		result.append(False)
		for i in range(1, n + 1):
			j = 1
			flag = True
			while j * j <= i:
				if not result[i - j * j]:
					flag = False
					break
				j += 1
			if flag == True:
				result.append(False)
			else:
				result.append(True)
		print(result)
		return result[-1]


from functools import lru_cache

class Solution:

	def winnerSquareGame(self, n: int) -> bool:
		dp = [None] * (n + 1)
		dp[0] = False
		i = 1
		while i ** 2 <= n:
			dp[i ** 2] = True
			i += 1
		sq = 1
		for i in range(2, n + 1):
			if dp[i]:
				continue
			dp[i] = False
			sq = int(math.sqrt(i))
			for k in range(sq, 0, -1):
				if not dp[i - k ** 2]:
					dp[i] = True
					break
		return dp[n]