一道有趣的广度优先搜索/动态规划的题
leetcode279 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
输入: n =12
输出: 3
解释:12 = 4 + 4 + 4.
输入: n =13
输出: 2
解释:13 = 4 + 9.
这是一道很有意思的题，我本来是搜索广度优先搜索的题目看到这道题的，但是乍一眼看上去这道题似乎和广度优先搜索没有关系，于是我就瞄了一眼题解，题解还有动态规划的解法，我用动态规划写出来之后发现时间效率只打败了5%的人，高达7000ms，我很疑惑，以为自己写错了，然后用高频题解的代码跑出来依然是这种情况，这就说明了这道题动态规划不是最优解，还有其他的解法。
先看动规的解法：
class Solution:
def numSquares(self, n: int) -> int:
dp=[0]*(n+1)
for i in range(n+1):
dp[i]=i
j=0
while (j+1)*(j+1)<=i:
j+=1
dp[i]=min(dp[i-j*j]+1,dp[i])
return dp[-1]
其实很好理解，就不在这解释了。
下面看广度优先搜索的解法，很有意思。
因为是广度优先遍历，顺序遍历每一行，所以当节点差出现0时，此时一定是最短的路径。
如绿色所示，若此时节点为0，表示根节点可以由路径上的平方数「1，1，9」构成，返回此时的路径长度3，后续不再执行。
如红色所示，若节点值在之前已经出现，则不需要再计算，一定不会是最短路径，就算有也是在前面先出现不是。
广度优先搜索一般要借助队列，这个题是一个层次遍历。
class Solution:
def numSquares(self, n: int) -> int:
from collections import deque
if n == 0: return 0
queue = deque([n])
step = 0
visited = set()
while(queue):
step+=1
l=len(queue)
for _ in range(l):
tmp=queue.pop()
for i in range(1,int(tmp**0.5)+1):
x=tmp-i**2
if(x==0):
return step
if(x not in visited):
queue.appendleft(x)
visited.add(x)
return step
我们来剖析一下这个代码，我们其实是要按照题意首要构建一棵树，子节点呢是根结点减去一些平方数之后的值，因为是广度优先，所以我们希望的是一层一层的来，也就是说我们希望先统计一层的信息，再把这一层的节点逐个pop出来，然后根据pop出来的结果呢来构建下一层的节点，所以我们就清楚了，广度优先搜索的时候我们氛围两个步骤，一个是统计本层的信息，一个是构建下一层的信息。广度优先搜索一般是用队列这种数据结构来构建的。如果是一颗已知的树，那么终止条件可以是把所有节点遍历完，但是我们需要考虑这个题的终止条件，因为所有的节点都是我们现场构造的，我们希望的又是出现一个结果0结束，那么我们的终止条件就是我们添加新节点时出现一个0，而且我们统计信息也已经在第一块内统计出来了，所以我们的统计信息直接返回回来就可以了，我们的最大的循环呢，也就是整个队列，我们是把一层都结束了，构建出下一层了，才进入下一个循环，也就是说最外面的while（queue）是针对每个循环的，此外，还有最重要的一点，这个题目要有剪枝操作，也就是说已经出现过的节点我们就不再考虑了，因为我们是按顺序来的，如果后面又出现已经出现过的节点，势必不能带来最佳的结果。
注意一下，写的时候出错了一个地方，就是对集合的定义：
s=set()而不是s=set{}