Stone Game IV - Problem Statement

$n$ stones. Each turn, remove a perfect square number of stones ($1$, $4$, $9$, ...). Can't move = lose. $dp[0] = false$. $dp[k^2] = true$ for all $k$ (take all, opponent gets 0). Transition: $dp[n] = \bigvee_{k^2 \leq n} \lnot dp[n - k^2]$. Try all valid square moves. Time: $O(n \sqrt{n})$.

Time complexity: $O(n \sqrt{n})$. For each state, try $O(\sqrt{n})$ moves. No simple closed form like Nim or Divisor Game. Unlike Nim, this has no simple closed form. The DP is necessary to determine winning positions.

Space complexity: $O(n)$ for the dp array.