https://leetcode.com/problems/stone-game-iv

In this problems we have game with two persons, and we need to understand who is winning, if they play with optimal strategies. In this game at each moment of time we have several (say k) stones, and we say that it is position in our game. At each step, each player can go from one position to another. Let us use classical definitions:

  1. The empty game (the game where there are no moves to be made) is a losing position.
  2. A position is a winning position if at least one of the positions that can be obtained from this position by a single move is a losing position.
  3. A position is a losing position if every position that can be obtained from this position by a single move is a winning position.

Why people use definitions like this? Imagine that we are in winning position, then there exists at least one move to losing position (property 2), so you make it and you force your opponent to be in loosing position. You opponent have no choice to return to winning position, because every position reached from losing position is winning (property 3). So, by following this strategy we can say, that for loosing positions Alice will loose and she will win for all other positions.

So, what we need to check now for position state: all positions, we can reach from it and if at least one of them is False, our position is winning and we can immedietly return True. If all of them are True, our position is loosing, and we return False. Also we return False, if it is our terminal position.

Complexity: For each of n positions we check at most sqrt(n) different moves, so overall time complexity is O(n sqrt(n)). Space complexity is O(n), we keep array of length n.

class Solution:
    def winnerSquareGame(self, n):
        
        @lru_cache(None)
        def dfs(state):
            if state == 0: return False
            for i in range(1, int(math.sqrt(state))+1):
                if not dfs(state - i*i): return True
            return False
        
        return dfs(n)

If you like the solution, you can upvote it on leetcode discussion section: Problem 1510