347. Stone Game IV

dp[i] answers: with i stones and me to move, can I win? I win if SOME square move jj leaves the opponent in a losing state — i.e. dp[i - jj] is False. Build dp[1..n] bottom-up; the answer is dp[n].

Winning vs losing positions

Think in terms of who is forced into a hopeless spot. Define dp[i] = true if the player to move, facing i stones, can force a win.

The recurrence

From i stones you may remove any perfect square j*j with j*j <= i, moving the opponent to i - j*j stones. You win if you can hand the opponent any losing position:

dp[i] = true  iff  there exists j with j*j <= i and dp[i - j*j] == false

If every square move lands the opponent on a winning position (dp[i - j*j] all true), then dp[i] = false — you are the one who loses. dp[0] = false: with no stones the player to move cannot move and loses.

Build dp from 1 up to n; the answer is dp[n].

Worked example

n = 17. Squares available: 1, 4, 9, 16.

• dp[0] = false (base — no move, you lose).
• dp[1] = true (remove 1 → opponent at dp[0]=false).
• dp[2]: only -1 → dp[1]=true. No losing move → false.
• dp[3]: -1 → dp[2]=false → true.
• dp[4]: -4 → dp[0]=false → true (also -1→dp[3]).
• dp[5]: -1→dp[4]=T, -4→dp[1]=T → false.
• ... continuing, dp[7] = false, dp[17] = false.

dp[17] = false, so with 17 stones the first player (Alice) loses → return false.

Complexity

• Time: O(n·√n) — each of n states scans up to √i square moves.
• Space: O(n) for the dp array.

class Solution {
    public boolean winnerSquareGame(int n) {
        // dp[i] = true if the player to move, facing i stones, can force a win.
        boolean[] dp = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                if (!dp[i - j * j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}