```
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
maxValue=2**31-1
ref=[maxValue]*(n+1)
ref[0]=0
for i in range(1, n+1):
if math.sqrt(i)==int(math.sqrt(i)):
ref[i]=1
else:
j=1
while j**2 < i:
ref[i]=min(ref[i], ref[i-j**2]+1)
j+=1
return ref[-1]
```