<p>Alice and Bob take turns playing a game, with Alice starting first.</p>

<p>Initially, there are <code>n</code> stones in a pile. On each player&#39;s turn, that player makes a <em>move</em> consisting of removing <strong>any</strong> non-zero <strong>square number</strong> of stones in the pile.</p>

<p>Also, if a player cannot make a move, he/she loses the game.</p>

<p>Given a positive integer <code>n</code>, return <code>true</code> if and only if Alice wins the game otherwise return <code>false</code>, assuming both players play optimally.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> true
<strong>Explanation: </strong>Alice can remove 1 stone winning the game because Bob doesn&#39;t have any moves.</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
</ul>

// class Solution {
// public:
//     vector<int> squares;
    
//     void init() {
//         for(int i=1;;i++){
//             int sq=i*i;
//             if(sq>1e5) break;
//             squares.push_back(sq);
//         }
//     }
    
//     int dp[100000][2];
    
//     int solve(int n, int c) {
//         if(n==0) return 1-c;
//         if(dp[n-1][c]!=-1) return dp[n-1][c];
//         auto it=upper_bound(squares.begin(),squares.end(),n)-squares.begin();
//         for(int i=it-1;i>=0;i--){
//             if(c==solve(n-squares[i],c^1)) return dp[n-1][c]=c;
//         }
//         return dp[n-1][c]=1-c;
//     }
    
//     bool winnerSquareGame(int n) {
//         init();
//         memset(dp,-1,sizeof(dp));
//         return solve(n,1);
//     }
// };

class Solution {
public:
    vector<int> squares;
    
    void init() {
        for(int i=1;;i++){
            int sq=i*i;
            if(sq>1e5) break;
            squares.push_back(sq);
        }
    }
    
    int dp[100000];
    
    int solve(int n) {
        if(n==0) return 0;
        if(dp[n-1]!=-1) return dp[n-1];
        auto it=upper_bound(squares.begin(),squares.end(),n)-squares.begin();
        for(int i=it-1;i>=0;i--){
            if(!solve(n-squares[i])) return dp[n-1]=1;
        }
        return dp[n-1]=0;
    }
    
    bool winnerSquareGame(int n) {
        init();
        memset(dp,-1,sizeof(dp));
        return solve(n);
    }
};
9593