LC-1510 Hard LeetCode

1510. Stone Game IV

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 59% Topics: Math, Dynamic Programming, Game Theory

Reading material

Math & Geometry 12 min 1-D Dynamic Programming 16 min Game Theory 11 min

Reference solution (spoiler · python)

# Time:  O(n * sqrt(n))
# Space: O(n)

class Solution(object):
    def winnerSquareGame(self, n):
        """
        :type n: int
        :rtype: bool
        """
        dp = [False]*(n+1)
        for i in xrange(1, n+1):
            j = 1
            while j*j <= i:
                if not dp[i-j*j]:
                    dp[i] = True
                    break
                j += 1
        return dp[-1]

Solution from kamyu104/LeetCode-Solutions · MIT