Stone Game IV — LeetCode 1510 Python Solution

The problem

Alice and Bob take turns playing a game, with Alice starting first. Initially, there are n stones in a pile.

Example

Input

n = 1

Output

true

Explanation

Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Python solution

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        @cache
        def dfs(i: int) -> bool:
            if i == 0:
                return False
            j = 1
            while j * j <= i:
                if not dfs(i - j * j):
                    return True
                j += 1
            return False

        return dfs(n)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1510. Stone Game IV is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems