Leetcode_Perfect Squares

Posted on | Edited on | In | Views:

Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
（将一个正整数分为干个平方数的和，使得平方数个数最少）

Example:



1. BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    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

2. 动态规划

1
2
3
4
5
6
7
8
9
10
class Solution:
    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