leetcode_perfect squares

class :
    def numSquares(self, n: int) -> int:
        queue = [n]
        count = 0
        while queue:
            tmp = []
            count += 1
            for q in queue:
                i = 1
                while i*i <= q:
                    v = q - i*i
                    if v == 0:
                        return count
                    tmp.append(v)
                    i += 1
            queue = tmp

class :
    def numSquares(self, n: int) -> int:
        dp = [1] + [0]*n
        for i in range(int(n**0.5), 0, -1):
            s = i**2
            for j in range(len(dp)):
                if dp[j] and j+s < len(dp) and not 0 < dp[j+s] < dp[j] + 1:
                    dp[j+s] = dp[j]+1
                    
        return dp[-1] - 1