Problem Description

The Stone Game IV problem on Leetcode presents a classic two-player game scenario. There are n stones in a pile. Two players (Alice and Bob) take turns; Alice always goes first. On a player's turn, they can remove any non-zero square number of stones (i.e., 1, 4, 9, 16, etc.) from the pile. The player who cannot make a move loses the game.

Given the total number of stones n, determine whether Alice (the first player) can win the game assuming both players play optimally.

• Input: n (integer, 1 ≤ n ≤ 10⁵)
• Output: True if Alice can win, False otherwise
• Players may only remove perfect square numbers of stones per turn
• Each stone can only be removed once (no reuse)
• There is always one valid solution for each input

Thought Process

To solve this problem, let's think about the game from the perspective of winning and losing positions:

• If it's your turn and every possible move leaves the opponent in a winning position, then you are in a losing position.
• If you can make at least one move that leaves the opponent in a losing position, then you are in a winning position.

For small values of n, we can manually play out the scenarios. However, as n increases, brute-force simulation becomes infeasible. Instead, we need a systematic way to determine for each state (number of stones left) whether the current player can force a win.

This leads us to the concept of dynamic programming, where we build up solutions for small values and use them to solve larger cases efficiently.

Solution Approach

We use dynamic programming to solve the problem efficiently. Let's break down the approach step by step:

1. Define the DP State:
   • Let dp[i] be True if the current player can win with i stones left, otherwise False.
2. Base Case:
   • dp[0] = False — With zero stones, the current player cannot move and loses.
3. Transition:
   • For each i from 1 to n, check all possible square numbers k*k such that k*k ≤ i.
   • If there exists any square number k*k where dp[i - k*k] == False, set dp[i] = True (current player can win by forcing the opponent into a losing state).
   • If all moves leave the opponent in a winning state, then dp[i] = False.
4. Result:
   • Return dp[n] as the answer.

This approach ensures we only compute each state once, leading to an efficient solution.

Example Walkthrough

Let's walk through an example with n = 7:

1. Possible moves for Alice: Remove 1 or 4 stones (since 9 > 7).
2. Option 1: Remove 1 stone
   • Stones left: 6
   • Now it's Bob's turn with 6 stones.
   • Bob can remove 1 or 4 stones.
   • If Bob removes 1 stone: 5 left for Alice.
   • If Bob removes 4 stones: 2 left for Alice.
3. Option 2: Remove 4 stones
   • Stones left: 3
   • Bob's turn with 3 stones. He can remove 1 stone (3-1=2) or 1 or 4 stones (4>3 so only 1).
   • Each sub-case can be traced further down, but with dynamic programming, we have already computed the result for smaller numbers.
4. Result: By filling in dp[1] to dp[7], we find that dp[7] = False. Alice cannot force a win if both play optimally.

Time and Space Complexity

• Brute-force approach:
  • For each state, try all possible moves recursively. This leads to exponential time complexity: O(2^n) in the worst case.
• Optimized DP approach:
  • For each i from 1 to n, we check up to O(\sqrt{n}) square numbers.
  • Total time complexity: O(n \sqrt{n}).
  • Space complexity: O(n) for the DP array.

The DP solution is efficient enough for n up to 10⁵.

Summary

The Stone Game IV problem is a classic example of using dynamic programming to analyze winning and losing positions in a turn-based game. By defining a DP state that tracks whether the current player can force a win, we avoid redundant calculations and solve the problem efficiently. The key insight is that a player is in a winning position if they can force the opponent into a losing position with any valid move. This approach is both elegant and practical for large input sizes.

Code Implementation

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        dp = [False] * (n + 1)
        for i in range(1, n + 1):
            k = 1
            while k * k <= i:
                if not dp[i - k * k]:
                    dp[i] = True
                    break
                k += 1
        return dp[n]
      

class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<bool> dp(n + 1, false);
        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k * k <= i; ++k) {
                if (!dp[i - k * k]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};
      

class Solution {
    public boolean winnerSquareGame(int n) {
        boolean[] dp = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k * k <= i; k++) {
                if (!dp[i - k * k]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}
      

var winnerSquareGame = function(n) {
    const dp = new Array(n + 1).fill(false);
    for (let i = 1; i <= n; i++) {
        for (let k = 1; k * k <= i; k++) {
            if (!dp[i - k * k]) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
};