import sys
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp=[float('inf')] * (n+1)
        m=int(n**(0.5)+1)
        dp[0]=0
        for x in range(1,m):
            for i in range(n+1):
                if i>=x**2:
                    dp[i]=min(dp[i],1+dp[i-x**2])
        print(dp)
        return dp[n]
n=112
s=Solution()
print(s.numSquares(n))