class Solution:
    def numSquares(self, n):
        f = [0] * (n + 1)
        for i in range(1, n + 1):
            minn = float('inf')
            j = 1
            while j * j <= i:
                minn = min(minn, f[i - j * j])
                j += 1
            f[i] = minn + 1
        return f[n]