Stone Game IV
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 square number of stones from the pile (i.e., 1, 4, 9, 16, ...). The player who cannot make a move loses the game (i.e., when the pile has 0 stones and it's their turn).
Given n, return true if Alice wins the game, assuming both play optimally.
Examples
Input: 1
Output: true
Input: 2
Output: false
Hints
This is an impartial combinatorial game solvable with DP. Define `dp[i] = true` if the current player can force a win from `i` stones.
A state is winning if there exists a square number `k*k <= i` such that `dp[i - k*k]` is false (i.e., the opponent loses from the resulting state).
Iterate from 1 to n, try all squares up to i. Complexity O(n*sqrt(n)) which is acceptable for moderate n.
Related Problems
Stone Game IV
Alice and Bob take turns playing a game, with Alice starting first.