**Solution**

**Perfect Squares** https://leetcode.com/problems/perfect-squares/

**Memoization based Solution**

- Draw a recursion tree with initial states being 1, 4, 9, 16...unit sqrt(N)

```
from math import sqrt
class Solution(object):
def helper(self, n, cache):
if n <= 1:
return n
elif n in cache:
return cache[n]
else:
s = int(sqrt(n))
cache[n] = float('inf')
for j in range(s,0,-1):
cache[n] = min(cache[n], self.helper(n-j*j, cache) + 1)
return cache[n]
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if n<= 1:
return 1
return self.helper(n, {})
```

**Breadth-First Solution**

- Can solve using BFS as well.