# Stone Game IV
**Difficulty:** HARD
[External](https://leetcode.com/problems/stone-game-iv)
Canonical: https://scaleengineer.com/dsa/problems/stone-game-iv
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
---
## Problem
Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are `n` stones in a pile. On each player's turn, that player makes a _move_ consisting of removing **any** non-zero **square number** of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer `n`, return `true` if and only if Alice wins the game otherwise return `false`, assuming both players play optimally.

**Example 1:**

**Input:** n = 1
**Output:** true
**Explanation:** Alice can remove 1 stone winning the game because Bob doesn't have any moves.

**Example 2:**

**Input:** n = 2
**Output:** false
**Explanation:** 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
**Explanation:** n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

**Constraints:**

* `1 <= n <= 105`

# Approaches
## Brute-Force Recursion
This approach directly translates the game's rules into a recursive function. A player wins if they can make a move that leaves the opponent in a losing state. The function recursively checks all possible moves (removing a square number of stones) to see if any lead to a losing position for the opponent.
**Time:** O(2^n) in the worst case. The recursion tree can grow exponentially as each call to `winnerSquareGame(n)` can result in up to `sqrt(n)` recursive calls. This leads to a massive number of redundant computations for the same subproblems. · **Space:** O(n) for the recursion stack depth in the worst-case scenario (e.g., when only 1 stone is removed at each step).
**Pros:** Simple to conceptualize and implement.; Directly models the logic of the game.
**Cons:** Extremely inefficient due to repeated calculations of the same subproblems.; Not feasible for the given constraints (n <= 10^5) and will result in a Time Limit Exceeded error.
### Explanation
This approach is a direct implementation of the recursive game theory logic. The core idea is that a player wins from a state `n` if they can make a move (subtracting `k*k` stones) to a state `n - k*k` from which the other player is guaranteed to lose. The function `winnerSquareGame(n)` checks this by trying every possible move. If any move leads to a state where the opponent loses (i.e., a recursive call returns `false`), the current player wins. If all moves lead to states where the opponent wins, the current player loses. This method is too slow because it re-calculates the result for the same number of stones multiple times, leading to an exponential number of calls.

```java
// This solution will result in Time Limit Exceeded.
class Solution {
    public boolean winnerSquareGame(int n) {
        if (n == 0) {
            return false;
        }
        for (int k = 1; k * k <= n; k++) {
            if (!winnerSquareGame(n - k * k)) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
*   Define a recursive function, say `winnerSquareGame(n)`.
*   The base case is `n = 0`, where the current player cannot move and loses. Return `false`.
*   Iterate through all possible moves by subtracting a square number `k*k` from `n`, where `1 <= k*k <= n`.
*   For each possible next state `n - k*k`, recursively call `winnerSquareGame(n - k*k)`.
*   If the recursive call returns `false`, it means the opponent will be in a losing position. Thus, the current player wins. Return `true` immediately.
*   If the loop completes without finding any such move, it means all moves lead to a winning position for the opponent. The current player loses. Return `false`.

## Top-Down Dynamic Programming with Memoization
This approach improves upon the brute-force recursion by using memoization to store the results of subproblems. By caching the outcome for each number of stones `i`, we avoid recomputing the same state multiple times, drastically reducing the time complexity.
**Time:** O(n * sqrt(n)). Each state `i` from 1 to `n` is computed only once. To compute the result for `i`, we iterate through `sqrt(i)` possible moves. The total work is the sum of `sqrt(i)` for `i` from 1 to `n`, which is bounded by `n * sqrt(n)`. · **Space:** O(n). This is for the memoization array of size `n+1` and the recursion stack, which can go up to depth `n` in the worst case.
**Pros:** Significantly more efficient than brute-force.; Guaranteed to solve the problem within the time limits.; Still maintains a readable, recursive structure.
**Cons:** May cause a `StackOverflowError` for very large `n` due to deep recursion, although it's generally fine for `n=10^5` in most competitive programming environments.
### Explanation
To optimize the brute-force recursion, we can use memoization. This technique stores the results of expensive function calls and returns the cached result when the same inputs occur again. We use an array, `memo`, to store the outcome (`true` for a win, `false` for a loss) for each number of stones from `0` to `n`.

Before computing the result for `n` stones, we first check if `memo[n]` has already been computed. If it has, we return the stored value immediately. Otherwise, we compute the result as in the recursive approach, and before returning, we store the result in `memo[n]`. This ensures that the subproblem for each number of stones is solved only once.

```java
class Solution {
    public boolean winnerSquareGame(int n) {
        // Use Boolean array to distinguish between not computed (null), win (true), and loss (false).
        Boolean[] memo = new Boolean[n + 1];
        return canWin(n, memo);
    }

    private boolean canWin(int n, Boolean[] memo) {
        if (n <= 0) {
            return false;
        }
        if (memo[n] != null) {
            return memo[n];
        }

        // Try all possible moves.
        for (int k = 1; k * k <= n; k++) {
            // If there is a move to a state from which the opponent cannot win, we win.
            if (!canWin(n - k * k, memo)) {
                memo[n] = true;
                return true;
            }
        }

        // If all moves lead to a winning state for the opponent, we lose.
        memo[n] = false;
        return false;
    }
}
```
### Algorithm
*   Create a memoization array, `memo`, of size `n + 1` to store the results of subproblems. Initialize it with a value indicating that the state has not been computed (e.g., `null`).
*   Define a helper function, say `canWin(n, memo)`.
*   Base case: If `n <= 0`, return `false`.
*   Memoization check: If `memo[n]` is not `null`, return the stored value.
*   Iterate through all possible moves by subtracting a square number `k*k` from `n`.
*   For each move, recursively call `canWin(n - k*k, memo)`.
*   If the recursive call returns `false`, it means we found a winning move. Store `true` in `memo[n]` and return `true`.
*   If the loop finishes without finding a winning move, store `false` in `memo[n]` and return `false`.
*   The main function initializes the memo array and calls the helper function.

## Bottom-Up Dynamic Programming
This is an iterative dynamic programming approach that builds the solution from the smallest subproblem up to the target `n`. It uses a DP array where `dp[i]` stores whether the first player can win with `i` stones. This avoids recursion and the associated overhead and potential stack depth issues.
**Time:** O(n * sqrt(n)). The outer loop runs `n` times, and for each `i`, the inner loop runs `sqrt(i)` times. The total complexity is the sum of `sqrt(i)` for `i` from 1 to `n`. · **Space:** O(n) to store the DP array of size `n+1`.
**Pros:** Highly efficient and avoids recursion overhead.; No risk of stack overflow errors.; Often slightly faster in practice than the memoized recursive solution.
**Cons:** Can be slightly less intuitive to write than the top-down recursive approach for some developers.
### Explanation
The bottom-up dynamic programming approach is an iterative alternative to the recursive solution. It solves the problem by building up a solution from smaller subproblems. We use a boolean array `dp` of size `n + 1`, where `dp[i]` represents whether the starting player can win with `i` stones.

We iterate from `i = 1` to `n`. For each `i`, we determine `dp[i]`. A player can win with `i` stones if they can make a move (remove `k*k` stones) to a state `i - k*k` where the opponent loses. In our DP table, this corresponds to finding a `k` such that `dp[i - k*k]` is `false`. If such a move exists, we set `dp[i]` to `true` and move to the next `i`. If after checking all possible moves from `i`, we don't find any that lead to a losing state for the opponent, `dp[i]` remains `false`. The final answer is `dp[n]`.

```java
class Solution {
    public boolean winnerSquareGame(int n) {
        boolean[] dp = new boolean[n + 1];
        // dp[0] is false by default, meaning a player with 0 stones loses.

        for (int i = 1; i <= n; i++) {
            // Check if there is any move to a losing position for the opponent.
            for (int k = 1; k * k <= i; k++) {
                if (!dp[i - k * k]) {
                    // If opponent loses from state i - k*k, then we win from state i.
                    dp[i] = true;
                    break; // Found a winning move, no need to check further for this i.
                }
            }
            // If the inner loop completes without setting dp[i] to true, it remains false.
        }
        return dp[n];
    }
}
```
### Algorithm
*   Create a boolean DP array, `dp`, of size `n + 1`. `dp[i]` will be `true` if the player starting with `i` stones wins.
*   `dp[0]` is implicitly `false` (or can be explicitly set), as a player with 0 stones loses.
*   Iterate from `i = 1` to `n`.
*   For each `i`, determine the value of `dp[i]`. Iterate through all possible moves `k*k` (where `k*k <= i`).
*   Check the state the opponent would be in: `dp[i - k*k]`.
*   If `dp[i - k*k]` is `false`, it means the current player can force the opponent into a losing position. Therefore, the current player wins. Set `dp[i] = true` and break the inner loop to move to the next `i`.
*   If the inner loop completes and `dp[i]` is still `false`, it means all moves lead to a winning state for the opponent, so the current player loses.
*   After the outer loop finishes, `dp[n]` holds the answer for the original problem.

# Solutions
### Java

```java
class Solution {
private
  Boolean[] f;
public
  boolean winnerSquareGame(int n) {
    f = new Boolean[n + 1];
    return dfs(n);
  }
private
  boolean dfs(int i) {
    if (i <= 0) {
      return false;
    }
    if (f[i] != null) {
      return f[i];
    }
    for (int j = 1; j <= i / j; ++j) {
      if (!dfs(i - j * j)) {
        return f[i] = true;
      }
    }
    return f[i] = false;
  }
}

```

### CPP

```cpp
class Solution { public: bool winnerSquareGame ( int n ) { int f [ n + 1 ]; memset ( f , 0 , sizeof ( f )); function < bool ( int ) > dfs = [ & ]( int i ) -> bool { if ( i <= 0 ) { return false ; } if ( f [ i ] != 0 ) { return f [ i ] == 1 ; } for ( int j = 1 ; j <= i / j ; ++ j ) { if ( ! dfs ( i - j * j )) { f [ i ] = 1 ; return true ; } } f [ i ] = - 1 ; return false ; }; return dfs ( n ); } };
```

### Python

```python
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 )
```