Stone Game IV

hard dp game theory math

Problem

Alice and Bob take turns, with Alice starting first. Initially there are n stones in a pile. On each turn the player removes a non-zero square number of stones. The player who cannot make a move loses. Assuming both play optimally, return true if and only if Alice wins.

Inputn = 7

Outputfalse

From 7 every square move (remove 1 or 4) leaves the opponent in a winning position, so Alice loses. dp[i] is true when the player to move with i stones can win.

def winner_square_game(n):
    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]

function winnerSquareGame(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];
}

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];
    }
}

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];
}

Explanation

This is a classic two-player game, so we reason about winning and losing positions. Let dp[i] be true when the player who faces a pile of i stones (and must move) can force a win.

With 0 stones the player to move cannot move and loses, so dp[0] = false. That is the base case the whole table is built on.

From i stones a player may remove any square number k*k <= i, handing the opponent a pile of i - k*k. The current player wins if some move leaves the opponent in a losing position: dp[i] = true if any dp[i - k*k] is false. If every square move lands the opponent in a winning spot, then dp[i] = false.

We fill dp from 1 up to n, and we can break as soon as one losing follow-up is found, since one good move is enough to claim the position. The answer is dp[n] — whether Alice, moving first with n stones, wins.

Example: n = 7. The only moves remove 1 or 4 stones, leaving 6 or 3 — both of which turn out to be winning positions for Bob. With no losing follow-up available, dp[7] = false, so Alice loses.

Time: O(n√n) Space: O(n)