0279：完全平方数（★）

1
2
3
4
5
6
7

class Solution:
    def numSquares(self, n: int) -> int:
        f = [0]+[inf]*n
        for x in range(1,n+1):
            for j in range(x*x,n+1):
                f[j] = min(f[j],1+f[j-x*x])
        return f[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def numSquares(self, n: int) -> int:
        Q, vis = deque([(0, 0)]), {0}
        while True:
            u,w = Q.popleft()
            for j in range(1,isqrt(n-u)+1):
                v = u+j*j
                if v==n:
                    return w+1
                if v not in vis:
                    vis.add(v)
                    Q.append((v,w+1))