279-perfect-squares.md

279. 完全平方数 - medium

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

 

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

 

提示：

• 1 <= n <= 104

Solutions

1. 动态规划

用 dp[i] 记录和为 i 所需最小完全平方个数。状态转移 dp[i] = min(dp[i], dp[i - v] + 1)

时间复杂度为 O(n * m) m 表示小于 n 的完全平方个数，等于根号 n。 空间复杂度为 O(n + m)

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [i for i in range(n + 1)]

        vs = []
        for i in range(n):
            v = i * i
            if v > n:
                break
            vs.append(v)
            dp[v] = 1
        
        for i in range(1, n + 1):
            for v in vs:
                if i <= v:
                    break
                dp[i] = min(dp[i], dp[i - v] + 1)
        
        return dp[-1]

优化版

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [i for i in range(n + 1)]

        vs = [i * i for i in range(1, int(n ** 0.5) + 1)]

        for i in range(1, n + 1):
            for v in vs:
                if i < v:
                    break
                dp[i] = min(dp[i], dp[i - v] + 1)
        
        return dp[-1]

2. 贪心算法

递归计算 count 次获取到和为 n 是否可能。count 从小往大，当为 True 时返回 count

class Solution:
    def numSquares(self, n: int) -> int:

        vs = [i * i for i in range(1, int(n ** 0.5) + 1)]

        def is_divided_by(n, count) -> bool:
            if count == 1:
                return n in vs
            
            for v in vs:
                if is_divided_by(n - v, count - 1):
                    return True
            return False
        
        for c in range(1, n + 1):
            if is_divided_by(n, c):
                return c
        return n

数学解法

当然自己想不出来。题解

数学证明，每个自然数都可以被表示为 4 个完全平方数的和（当 n 本身就是平方和时，表示为 n + 0^2 ... + 0^2）。当 n != 4^k * (8 * m + 7) 时，可以表示为 3 个平方和。

我们要求最小平方和个数。当 n != 4^k * (8*m + 7) 时，要一次判断是为本身为平方数和；是否为两个数平方和。

class Solution:
    def numSquares(self, n: int) -> int:
    
        while n % 4 == 0:
            n //= 4
        
        if n % 8 == 7:
            return 4

        if self.is_sequares(n):
            return 1

        vs = [i * i for i in range(1, int(n ** 0.5) + 1)]
        for v in vs:
            if self.is_sequares(n - v):
                return 2

        return 3
        
        
    def is_sequares(self, n):
        v = int(n ** 0.5)
        return v * v == n