Stone Game IV: Game Theory Meets Dynamic Programming

Alice and Bob play a game with n stones. They take turns, and Alice goes first. On each turn, the current player must remove a perfect square number of stones (1, 4, 9, 16, ...). The player who cannot make a move (because there are 0 stones left) loses. Given n, return true if Alice can win assuming both players play optimally.

This is LeetCode 1510: Stone Game IV, and it combines two ideas you have probably seen separately: game theory (who wins with optimal play?) and dynamic programming (how do we efficiently evaluate every game state?). The key insight is that each stone count maps to exactly one of two states, winning or losing, and you can build a DP table that captures all of them.

Why this problem matters

Stone Game IV is a clean example of game-state DP. Unlike problems where you optimize a score or count paths, here the DP stores a boolean: "can the current player win from this state?" The transition asks a fundamentally different question: "does there exist at least one move that puts the opponent in a losing state?"

This pattern shows up across the entire Stone Game family and in classic combinatorial game theory. Once you see it here, you will recognize it in problems involving Nim, Sprague-Grundy values, and any game where players alternate turns with perfect information.

The problem also tests your understanding of perfect squares. The set of available moves at each state is not fixed (like "take 1, 2, or 3" in Nim Game). Instead, it depends on how many stones remain, since larger perfect squares become available as n grows.

Starting with the game tree

Think about small cases first. With 0 stones, the current player cannot move and loses. With 1 stone, you take 1 (which is 1*1) and your opponent faces 0 stones, so you win.

With 2 stones, you can only take 1 (since 4 > 2). That leaves your opponent with 1 stone, and they win. So you lose with 2.

With 3 stones, take 1, leaving your opponent with 2. We just established that 2 is a losing position. Your opponent loses, so you win.

With 4 stones, you have two choices: take 1 (leaving 3, a winning position for the opponent) or take 4 (leaving 0, a losing position for the opponent). Taking 4 works, so you win.

The pattern of wins and losses is not periodic like the Nim Game. It depends on which perfect squares fit, and that makes a closed-form solution unlikely. DP is the right tool.

The DP formulation

Define dp[i] as True if the current player can win with i stones, and False otherwise.

The recurrence:

• dp[0] = False (no stones, current player loses)
• For each i from 1 to n, check every perfect square sq where sq <= i. If dp[i - sq] is False for any such sq, then dp[i] = True.
• If no perfect square leads to a losing state for the opponent, then dp[i] = False.

In other words, you win if you can find even one move that puts your opponent in a losing position. You lose only if every possible move leaves your opponent winning.

The solution

def winnerSquareGame(n):
    dp = [False] * (n + 1)

    for i in range(1, n + 1):
        j = 1
        while j * j <= i:
            if not dp[i - j * j]:
                dp[i] = True
                break
            j += 1

    return dp[n]

The outer loop fills dp[1] through dp[n]. The inner loop tries every perfect square j*j that fits. As soon as we find one that lands on a losing state, we set dp[i] = True and break early. If no perfect square works, dp[i] stays False.

Step-by-step walkthrough

Let's trace through n = 7 to see how the DP table fills. The perfect squares that matter are 1 (11) and 4 (22), since 9 (3*3) exceeds 7.

Notice the alternating clusters of W and L values. This is not a simple repeating pattern. At dp[4], the availability of a new perfect square (4) creates a winning position that would otherwise be a loss. Every time a new perfect square becomes reachable, it can flip a losing state to a win.

The answer for n = 7 is dp[7] = False. Alice loses with optimal play from both sides.

Complexity analysis

Time: O(n * sqrt(n)). For each of the n states, we iterate over perfect squares up to i. The number of perfect squares up to i is at most sqrt(i). Summing sqrt(i) for i from 1 to n gives O(n * sqrt(n)) total work. The early break helps in practice but does not change the worst case.

Space: O(n). One boolean array of length n + 1.

Building blocks

This problem is built on game-state DP with boolean transitions, the same fundamental pattern as Nim Game. The structure is: iterate through possible game states, and at each state determine win or loss based on previously computed states.

The difference from Nim Game is the set of moves. In Nim Game, you can take 1, 2, or 3 stones, and the result collapses to a simple n % 4 != 0 check. Here, the moves are all perfect squares up to the current count, and no simple modular pattern emerges. That is why DP is necessary.

The same building block shows up in other problems:

• Nim Game (LeetCode 292): same win/loss game DP, but the fixed move set (1, 2, 3) allows a modular shortcut.
• Stone Game (LeetCode 877): two-player game with interval DP and a mathematical proof that the first player always wins.
• Divisor Game (LeetCode 1025): same boolean DP idea, but the move is to subtract any divisor of the current number.

Once you see the shared pattern (boolean DP, "exists a move to a losing state"), these problems become variations on the same theme.

Edge cases to watch for

• n = 0: return False. No stones means the current player loses immediately. (This case may not appear in the constraints, but the DP handles it naturally.)
• n = 1: return True. Take the single stone.
• n is a perfect square: not always a guaranteed win. For example, n = 4 is a win (take all 4), but the general case depends on the full DP.
• Large n: the constraint allows up to 100,000. The O(n * sqrt(n)) solution handles this comfortably since sqrt(100,000) is about 316, giving roughly 31.6 million operations.
• Consecutive losses: positions like dp[2], dp[5], and dp[7] are all losses. There is no predictable spacing between losing positions.

From understanding to recall

You have just traced through the game-state DP for Stone Game IV. The recurrence is simple: check all perfect squares, and if any one leads to a losing state for the opponent, you win. But will you remember three things a week from now? First, that dp[0] = False (not True). Second, that you iterate over perfect squares with j*j, not a fixed set. Third, that you break as soon as you find a single winning move.

Understanding and recall are different skills. The gap between "I get it" and "I can write it cold" is bigger than most people expect. Spaced repetition closes that gap. You revisit the game-state DP pattern at increasing intervals, write the recurrence from scratch each time, and after a few reps the pattern is second nature.

The game-state DP with boolean transitions pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Nim Game - The simplest game-state problem, same win/loss logic with a modular shortcut
• Stone Game - Two-player game with interval DP and a mathematical proof for the first player
• Coin Change - Same DP table structure (iterate states, check all valid moves), but optimizing a count instead of a boolean