#1510

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Stone Game IV

Stone Game IV requires predicting the winner using state transition dynamic programming with careful consideration of perfect square moves.

math dynamic programming game theory

Problem Statement

Alice and Bob play a turn-based game starting with a pile of n stones. On each turn, the current player must remove a number of stones that is a perfect square. The first player unable to make a move loses the game.

Given an integer n representing the initial number of stones, determine if Alice can guarantee a win assuming both players play optimally. Output true if Alice can win and false otherwise.

Examples

Example 1

Input: n = 1

Output: true

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

Example 2

Input: n = 2

Output: false

Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3

Input: n = 4

Output: true

n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Constraints

1 <= n <= 105

Solution Approach

Dynamic Programming Array

Create a DP array where dp[i] represents if the current player can win with i stones. Initialize dp[0] = false since no stones means a loss. Iterate from 1 to n, checking all square numbers k _k <= i. If removing k_k stones leads to a losing state dp[i - k*k] = false, mark dp[i] = true.

Iterative State Transitions

For each pile size i, consider all possible perfect square moves. Use the state transition: dp[i] = any(!dp[i - k*k]). This ensures that dp[i] correctly reflects the ability to force the opponent into a losing state, capturing the exact state transition DP pattern of this problem.

Optimizing with Square Limits

Precompute all perfect squares up to n to reduce repeated calculations. This avoids redundant loops and ensures the DP computation remains efficient for large n, directly addressing the failure mode of slow computation when repeatedly checking squares.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * sqrt(n)) because for each i from 1 to n we check up to sqrt(i) perfect square moves. Space complexity is O(n) to store the DP array representing winning and losing states for each pile size.

What Interviewers Usually Probe

Ask if you considered precomputing squares to improve DP efficiency.
Expect you to explain how dp[i] = any(!dp[i - k*k]) captures winning states.
Check if you correctly handle edge cases like n = 0 or small perfect squares.

Common Pitfalls or Variants

Common pitfalls

Failing to consider all possible perfect square moves for each state.
Incorrectly initializing dp[0], leading to wrong outcomes for small n.
Confusing the state meaning, marking dp[i] as true when it does not force a loss on the opponent.

Follow-up variants

Change the removal rule to cubes instead of squares to test DP adaptability.
Play with multiple piles and allow removing squares from any pile, increasing state space complexity.
Modify the first player to Bob and ask for the winning strategy under the same DP framework.

FAQ

What is the key pattern to solve Stone Game IV?

The key pattern is state transition dynamic programming, where each dp[i] depends on smaller piles and perfect square removals.

How do I handle small n values in Stone Game IV?

Initialize dp[0] = false and compute dp[1] through dp[n] iteratively, checking all perfect square moves for each i.

Can this approach scale to n = 10^5?

Yes, by precomputing all squares up to n and using the O(n*sqrt(n)) DP approach, it scales efficiently.

Why does Alice sometimes lose even when n is small?

If every perfect square removal leaves Bob in a winning state, Alice cannot force a win, demonstrating the state transition logic.

Does GhostInterview help identify optimal moves in Stone Game IV?

Yes, it pinpoints which stone removals lead to winning states and visualizes the DP transitions for strategic decision-making.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)

Continue Practicing

#1563 stone game v #1406 stone game iii #1690 stone game vii