Loading 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 removes the single stone (1 = 1^2) and Bob has no move, so Bob loses. Alice wins.
Example 2
Input: n = 2
Output: false
Explanation: Alice can only remove 1, leaving 1 for Bob, who removes it and leaves Alice stuck. Alice loses.
Example 3
Input: n = 4
Output: true
Explanation: Alice removes all 4 (2^2) at once, leaving Bob with nothing. Alice wins.
dp[i] answers: with i stones and me to move, can I win? I win if SOME square move j*j leaves the opponent in a losing state — i.e. dp[i - j*j] is False. Build dp[1..n] bottom-up; the answer is dp[n].
Run checks all cases above. Submit evaluates all test cases.