279.完全平方数

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

示例 1:

输入: n = 12 输出: 3  解释: 12 = 4 + 4 + 4. 

示例 2:

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

【中等】
【分析】BFS，利用自带你seen来记录当前应该被分解的数字，记录当前数字之前已经被分解的次数，当该数字被访问过时，不加入队列。

class Solution:     def numSquares(self, n: int) -> int:         queue=[n] # 记录当前应该被分解的数字以及在此之前已经被分解的次数         seen={n:0}         while queue:             num=queue.pop(0)                           i=1             while i<=num and num-i**2>=0:                 nums=num-i**2   #将num分解到nums                 if nums==0:                     return seen[num]+1                 if nums not in seen:                     queue.append(nums)                     seen[nums]=seen[num]+1                     i+=1 

【分析2】动态规划
定义状态和状态转移方程

class Solution:     def numSquares(self, n: int) -> int:         dp=[float("inf") for _ in range(n+1)]         dp[0]=0         for i in range(1,n+1):             j=1             while j<=i and i-j*j>=0:                 dp[i]=min(dp[i],dp[i-j*j]+1)                 j+=1         return dp[-1] 

上面的代码时间超出限制，。
改进，将上面while换成了直接在

i−j∗j>=0即1<=j<=i​范围内直接求所有

dp[i−j∗j]们的最小值：

class Solution:     dp_=[0]     def numSquares(self, n: int) -> int:         dp=self.dp_         for num in range(1,n+1):             dp+=[min(dp[num-i*i]+1 for i in range(1,int(num**0.5+1)))]         return dp[-1] 

【分析3】四平方和定理

    Lagrange 四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。 

if and only if n is not of the form

n=4a(8b+7) for integers a and b.