LC1510. Stone Game IV

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        """ tc O(Nsqrt(N))  sc O(N)
        
        """
        #dp[i] will player win with i stone 
        dp = [False]*(n+1)
        #dp[1] = True  
        for i in range(1,n+1):
            for k in range(1,int(sqrt(i))+1):
                if dp[i-k*k] == False:  # i - k*k >= 0 next player will lose ==> current player must win  
                    dp[i] = True  
                    break
        return dp[n]

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        """ tc O(Nsqrt(N))  sc O(N)
        
        """
        #dp[i]== False Alice player win with i stone, dp[i] == False : bob must win 
        dp = [False]*(n+1)
        for a in range(n+1):
            if dp[a]:
                continue 
            for k in range(1,int(sqrt(n))+1):
                if a + k*k <= n: # assuming i can go to a by removing b*b steps
                    dp[a + k*k] = True
                else:
                    break
        return dp[n]