完全平方数

Leetcode Link: 279. 完全平方数 - 力扣（LeetCode）

题目

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

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

解法一

思路：暴力递归

这个比较简单，就是不停的往下尝试

定义函数 def process(tar)，返回和为 tar 的完全平方数的最少数量。

细节：

• 注意遍历的时候，不能从 0 开始，不然爆栈
• 遍历时，我们其实可以提前指定遍历的最大值，为int(sqrt(tar))，并且这个值是可以取到的。

题解：

class Solution:
    def numSquares(self, n: int) -> int:
 
        @cache
        def process(tar):
            if tar == 0: # base case
                return 0
            
            res = float('inf')
            for i in range(1, int(sqrt(tar))+1): # 注意两边，最后要+1，以取到int(sqrt(tar))
                res = min(res, process(tar-i**2)+1)
            return res
        
        return process(n)

解法二

思路： 改写解法一为动态规划，直接抄就行

题解：

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] * (n+1)
        # 初始化条件就是dp[0] = 0
        for tar in range(1, n+1):
            res = float('inf')
            for i in range(1, int(sqrt(tar))+1):
                res = min(res, dp[tar-i**2]+1)
            dp[tar] = res
        return dp[n]

---

复习时写的会超时的动规

class Solution:
    def numSquares(self, n: int) -> int:
        length = int(sqrt(n))+1 # 最大用的数字
    
        @cache
        def process(i, tar):
            nonlocal length
            if tar == 0:
                return 0
            times = 0 # 用多少次
            res = float('inf')
            ii = i**2
            while(tar-times*ii>=0 and i+1<=length):
                res = min(res, process(i+1, tar - times*ii) + times)
                times += 1
 
            return res
        
        return process(1, n)

原因分析

可能是这个dp有两个参数，i 和tar，导致能够保存的状态不够多。

解法三

思路：数学，四平方和定理

四平方和定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。推论：满足四数平方和定理的数 n（四个整数的情况），必定满足如下等式 $n=4^a(8b+7)$

题解：

 def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        while n % 4 == 0: 
            n /= 4 
        if n % 8 == 7: 
            return 4 
        a = 0 
        while a**2 <= n: 
            b = int((n - a**2)**0.5) 
            if a**2 + b**2 == n: 
                return (not not a) + (not not b) 
            a += 1 
        return 3

启发和联系

其实本题本质上属于硬币问题，改写一下为： 已知target为n，硬币集合为[一堆合理的完全平方数]，每个硬币可以用无数次，找最小的组成个数。