给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
路径最短的问题 使用BFS最优
BFS其实是很简单的算法，只需要掌握以下几个套路
1.BFS算法组成的三要素：队列、入队及出队的结点、已经访问的标记集合
队列：先入先出的容器
入队、出队的结点
已访问标记集合：避免队列插入重复的值
2.BFS算法组成的格式
（1）初始化元素
queue<int>qq;
vector<int>visited(n+1);
（2）操作队列---弹出队首节点
int num=qq.front();
qq.pop();
····（3）操作弹出的节点 —— 根据业务生成子节点（一个或多个）：
for(int i=1;i<=static_cast<int>(sqrt(num));i++)
int temp=num-i*i;
（4）判断这些节点 —— 符合业务条件，则return，不符合业务条件，且不在已访问集合，则追加到队尾，并加入已访问集合：
if(temp==0) return step;
else if(!visited[temp])
{
qq.push(temp);
visited[temp]=true;
}
(5)若以上遍历完成仍未return，下面操作返回未找到代码：return -1;
class Solution{ public: int numSquares(int n) { int step=0; queue<int>qq; vector<int>visited(n+1); qq.push(n); visited[n]=true; while(!qq.empty()) { int size_=qq.size(); step++; for(int j=0;j<size_;j++) { int num=qq.front(); qq.pop(); for(int i=1;i<=static_cast<int>(sqrt(num));i++) { int temp=num-i*i; if(temp==0) return step; else if(!visited[temp]) { qq.push(temp); visited[temp]=true; } } } } return -1; } };