<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:
    def winnerSquareGame(self, n: int) -> bool:
        '''
        * game starts with alice and n stones in a pile.. 
        * a player remove square number of stones in each turn.. if they can't find a square number of stones to remove.. they lose.. 
        * if both alice and bob plays optimally, return true if alice can win the game.. 
        ====
        * I can simulate the game --> but 1 <= n <= 10**5; might not get accepted.. 
        * what would optimally mean here? => on each turn they should take the biggest square number of stones possible out.. that way next player will be left with nothing (or at least left with non square stones..)
        '''
        @cache
        def helper(n): 
            if n == 0: return False # no stones left to play.. 

            for square_num in range(1, int(math.sqrt(n)) + 1)[::-1]: # all the square number that can be made with this n stones in reverse.. 
                if not helper(n - (square_num * square_num)): # alice take out(square_num * square_num).. recursively simulate and check if there is at least one scenario in which bob loses.. 
                    return True # alice wins!
            return False

        return helper(n)
20730