Stone Game IV - Implementation

Precompute perfect squares up to $n$: $[1, 4, 9, 16, ...]$. For each state, iterate through valid squares. Early termination: if any move leads to a losing state, we win. Stop as soon as we find one. Memoization: use array $dp[0..n]$. Fill bottom-up since $dp[n-k^2]$ is always smaller than $dp[n]$. Space: $O(n)$. Time: $O(n \sqrt{n})$ worst case, but early termination helps in practice. Precompute all perfect squares up to n. This avoids repeated square root computations in the inner loop.

Time complexity: $O(n \sqrt{n})$.

Space complexity: $O(n)$.