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.

&nbsp;
Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -&gt; 1 -&gt; 0).


Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -&gt; 0).


&nbsp;
Constraints:


	1 &lt;= n &lt;= 105


class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        squares = lambda x: (i * i for i in range(isqrt(x), 0, -1))
        
        @cache
        def can_win(n: int) -> bool:
            return n and not all(can_win(n - s) for s in squares(n))
        
        return can_win(n)
class Solution {
    // idea: Alice wins a game with n stones if and only if there exists
    // some perfect square p <= n such that Alice wins a game with
    // n - p stones... i.e., Bob DOES NOT win a game with n - p stones
    public boolean winnerSquareGame(int n) {
        // this bit would be better with just an array of booleans, but this
        // is how i thought of it at the time, so leaving it this way...
        // maybe it will be "more explicit" and help someone better understand dp?
        HashMap<Integer, Boolean> memo = new HashMap<>();
        memo.put(1, true); // if there is one stone in the pile to begin the game, the next player to go wins
        memo.put(0, false); // if there are zero stones in the pile to begin the game, the next player to go loses
        List<Integer> perfectSquares = new ArrayList<>();
        int i = 1;
        while (i * i <= n) {
            perfectSquares.add(i * i);
            i++;
        }
        // if there are some perfect square number of stones in the pile to begin the game, the next player to go wins
        perfectSquares.forEach(p -> memo.put(p, true));
        // Alice goes first...
        return this.playerWins(n, perfectSquares, memo);
    }

    private boolean playerWins(int n, List<Integer> P, HashMap<Integer, Boolean> m) {
        if (m.containsKey(n)) { return m.get(n); } // if we already computed the answer for n, just return it
        m.put(n, false); // otherwise, assume it's false to begin...
        for (Integer p : P) { // check every perfect square p...
            if (p <= n && !playerWins(n - p, P, m)) {
                // if p <= n AND the player who goes next (e.g., Bob) does not win a game that begins with
                // n - p stones, then we know that the player whose turn it is right now (e.g., Alice) wins
                // a game that begins with n stones, so record this discovery in the memo and then break out
                // of the loop because there's no more work to do...
                m.put(n, true);
                break;
            } // else p >= n OR taking p stones would not result in a win for the player whose turn it is right now...
        }
        // we put false in before the loop; if we never found a reason to change it to true,
        // then false is the correct result...
        return m.get(n);
    }

}
class Solution {
public:
    bool winnerSquareGame(int n) {

        vector<int> dp(n+1,false);

        for(int i=1;i<=n;i++){
            for(int j=sqrt(i);j>=1;j--){
                if(dp[i-j*j] == false){
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};
var winnerSquareGame = function(n) {
    
    const map = new Map();
    map.set(0, false);
    map.set(1, true);
    
    const dfs = (num) => {
        if( map.has(num) ) return map.get(num);
        let sqRoot = Math.floor(Math.sqrt(num));
        
        for(let g=1; g<=sqRoot; g++){
            if( !dfs(num - (g*g)) ) {
                map.set(num, true);
                return true;
            }    
        }
        map.set(num, false);
        return false;
    }
    
    return dfs(n)
};
Stone Game IV