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).
Constraints:
1 <= n <= 105
- code if while i*i <= num, don’t need to check sqr
class Solution:
def winnerSquareGame(self, n: int) -> bool:
memo ={}
def dp(num):
if num in memo: return memo[num]
sqr = num ** 0.5
if sqr == int(sqr):
memo[num] = True
return True
res = False
i = 1
while i * i < num:
if not dp(num - i * i):
res = True
break
i += 1
memo[num] = res
return res
return dp(n)
- code
class Solution:
def winnerSquareGame(self, n: int) -> bool:
@lru_cache(maxsize=None)
def dfs(remain):
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)
- code
class Solution:
def winnerSquareGame(self, n: int) -> bool:
dp = [False]*(n+1)
for i in range(1, n+1):
for k in range(1, int(i**0.5)+1):
if dp[i-k*k] == False:
dp[i] = True
break
return dp[n]
- code quickest
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]
Let’s think in the backtrack way. If we have a state i that we know the current player must lose, what can we infer? – Any other states that can go to i must be True.