```
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
dp = [float('inf')]*(n+1)
dp[0]=0
count = 2
for i in range(1,n+1):
if i>=count*count:
count += 1
for j in range(1,count):
dp[i] = min(dp[i],dp[i-j*j]+1)
return dp[n]
```