class Solution:
    def numSquares(self, n):
        squares = []
        k = 2
        while k * k <= n:
            squares.append(k * k)
            k += 1

        nums = [0] * (n + 1)
        for k in range(1, n + 1):
            nums[k] = 1 + nums[k-1]
            for s in squares:
                if s > k:
                    break
                if nums[k-s] < nums[k]:
                    nums[k] = 1 + nums[k-s]

        return nums[n]