class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp=[0]
        while len(dp)<=n:
            dp+=min(dp[-i*i] for i in xrange(1,int(len(dp)**0.5+1)))+1,
        
        return dp[n]

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp=[n]*(n+1)
        dp[0]=0
        dp[1]=1
        
        for i in xrange(2,n+1):
            a=1
            while a*a<=i:
                dp[i]=min(dp[i],dp[i-a*a]+1)
                a+=1
            #print i,dp[i]
        return dp[n]