``````class Solution {
public:
int numSquares(int n) {
int sum = 0;
int num = n;
int cnt = 0;
while(num > 0) {
while(n >= sum + num && is_squares(num))
{
sum += num;
cnt += 1;
if(sum == n) return cnt;
}
num--;
}
return cnt;
}
private:
bool is_squares(int n){
int num = sqrt(n);
if(num * num == n)
return true;
return false;
}
};``````

``````Submission Detail
312 / 588 test cases passed.
Submitted: 4 minutes ago
Input:
12
Output:
4
Expected:
3``````

``````bool is_squares(int n){
if(sqrt(n) * sqrt(n) == n)
return true;
return false;
}``````

``````class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
dp[0] = 0;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j*j <= i;j++)
dp[i] = min(dp[i],dp[i-j*j] + 1);
}
return dp[n];
}
};``````

``````Runtime: 184 ms, faster than 53.88% of C++ online submissions for Perfect Squares.
Memory Usage: 9 MB, less than 66.35% of C++ online submissions for Perfect Squares.``````

BFS方式实现

``````class Solution {
public:
int numSquares(int n) {
//去重 保存已求得的和
unordered_set<int> visited;
queue<int> q;
//保存小于等于n的完全平方数
vector<int> perfect;
int step = 1;
for(int i = 1;i*i<=n;i++)
{
int num = i*i;
q.push(num);
perfect.push_back(num);
visited.insert(num);
}
//如果最后一个元素等于n，则只需要一个
if(q.back() == n) return 1;

while(!q.empty())
{
step += 1;
int size = q.size();
for(int i = 0;i < size;i++)
{
int num = q.front();
for(auto elem : perfect)
{
//遍历完全平方数vector，每次相加判断和n的关系
int sum = num + elem;
if(sum > n) break;
if(sum == n) return step;
if(sum < n && !visited.count(sum))
{
visited.insert(sum);
q.push(sum);
}
}
q.pop();
}
}

return -1;
}
};``````

``````Runtime: 112 ms, faster than 74.35% of C++ online submissions for Perfect Squares.
Memory Usage: 26.2 MB, less than 11.14% of C++ online submissions for Perfect Squares.``````