Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n =12
Output: 3
Explanation:12 = 4 + 4 + 4.
Example 2:
Input: n =13
Output: 2
Explanation:13 = 4 + 9.
-----------------------------------------------------------------------------
这个题可以用BFS，不过要注意排除重复的。
C++代码：
class Solution {
public:
int numSquares(int n) {
if(n == )
return ;
queue<pair<int,int> > q;
q.push(make_pair(n,));
vector<bool> vis(n+,false); //用这个来避免把重复的数加进队列。
vis[n] = true;
while(!q.empty()){
int num = q.front().first;
int s = q.front().second;
q.pop();
if(num == )
return ;
for(int i = ; num - i*i >= ; i++){
int ans = num - i*i;
if(ans == )
return s;
if(!vis[ans]){
q.push(make_pair(ans,s+));
vis[ans] = true;
}
}
}
return ;
}
};