Stone Game IV

'''
Bottom up DP
dp[i]: is it possible to make a winning move with i stones left ?
dp[i] = True €x: dp[x] = False for any x such that i-x is perfect square
Base case: dp[0] is false

For a player to win he must have a move to make the opposite player lose
If a player has no move to make opposite player lose then he lose, coz the other player will have a move to make him lose
'''
class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        dp = [False]*(n+1)
        for i in range(n+1):
            if dp[i] == False:
                j = 1
                while (k := i + j*j)<=n:
                    dp[k] = True
                    j += 1
            if dp[n] == True:
                return True
        return dp[n]