题目
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.
解题思路
dp, dp[i]=True表示先手赢，False表示先手输，dp[0]=False, dp[i] = any(dp[i-j*j]=False) i >= j * j
代码
class Solution:
def winnerSquareGame(self, n: int) -> bool:
dp = [False] * (n + 1)
for i in range(n + 1):
j = 1
while j * j <= i:
if not dp[i - j * j]:
dp[i] = True
break
j += 1
return dp[n]
