```
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
cnt=[n+1]*(n+1)
sqs=set()
i=1
while i*i<=n:
sqs.add(i*i)
i+=1
sqso=sorted(sqs)
ind=0 #my_xrange(0)
sqsosub=[]
for i in xrange(1,n+1):
if i in sqs:
cnt[i]=1
ind+=1
sqsosub.append(sqso.pop(0))
else:
for j in sqsosub:
cnt[i]=min(cnt[i],cnt[i-j]+1)
return cnt[n]
```