<p>Given an integer <code>n</code>, return <em>the least number of perfect square numbers that sum to</em> <code>n</code>.</p>

<p>A <strong>perfect square</strong> is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, <code>1</code>, <code>4</code>, <code>9</code>, and <code>16</code> are perfect squares while <code>3</code> and <code>11</code> are not.</p>

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

<pre>
<strong>Input:</strong> n = 12
<strong>Output:</strong> 3
<strong>Explanation:</strong> 12 = 4 + 4 + 4.
</pre>

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

<pre>
<strong>Input:</strong> n = 13
<strong>Output:</strong> 2
<strong>Explanation:</strong> 13 = 4 + 9.
</pre>

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

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

from math import sqrt
INFTY = 10**4
class Solution:
    def numSquares(self, n: int) -> int:
        best_to_target = {0: INFTY}

        best_from = {0: 0}
        # prepopulate squares since they're easy to hit
        for i in range(1, int(sqrt(n)) + 1):
            # print(i**2)
            best_from[i**2] = 1

        def bfs(target, count):
            if best_from.get(target) is not None:
                return best_from[target] + count
            # print(target, count)
            # if we can't beat our best count so far, prune early
            if (count > best_to_target.get(target, INFTY)) or (count > best_to_target[0]):
                return INFTY
            else:
                # if we beat our previous best to this target, update
                best_to_target[target] = count
            best = INFTY
            # check up to sqrt(target)
            for i in range(1, int(sqrt(target)) + 1)[::-1]:
                # we hit our target! no need to keep recursing
                if target == i ** 2:
                    # update fastest time to zero
                    best_to_target[0] = min(best_to_target[0], count + 1)
                    # we have a new global record
                    best_from[n] = count + 1
                    # and new local record
                    best_from[target] = 1
                    return count + 1
                    break
                
                    
                # otherwise spawn a new search from this
                best = min(best, bfs(target - i**2, count+1))

                # print(target, i, best)

            # store best 
            # print(target, best, count)
            best_from[target] = best - count
            return best


        count =  bfs(n, 0)
        # print(best_from)

        return count
        
        
37864