```
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
memo = [-1]*n
for i in range(1,n+1):
if memo[i-1] > 0 :
return
root = int(math.floor(math.sqrt(i)))
val = root * root
if val == i:
memo[i-1] = 1
else:
mins = 1 + memo[i-val-1]
for j in range(root-1,0,-1):
a = 1 + memo[i-j*j-1]
if a < mins:
mins = a
memo[i-1] = mins
return memo[n-1]
```