# 279. Perfect Squares

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.
``````

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

``````class Solution {
public:
int numSquares(int n) {
while (n % 4 == 0) n /= 4;
if (n % 8 == 7) return 4;
for (int a = 0; a * a <= n; ++a) {
int b = sqrt(n - a * a);
if (a * a + b * b == n) {
return !!a + !!b;
}
}
return 3;
}
};
``````

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

``````class Solution {
public:
int numSquares(int n) {
vector<int> dp(1, 0);
while (dp.size() <= n) {
int m = dp.size(), val = INT_MAX;
for (int i = 1; i * i <= m; ++i) {
val = min(val, dp[m - i * i] + 1);
}
dp.push_back(val);
}
return dp.back();
}
};
``````

``````class Solution {
public:
int numSquares(int n) {
int res = n, num = 2;
while (num * num <= n) {
int a = n / (num * num), b = n % (num * num);
res = min(res, a + numSquares(b));
++num;
}
return res;
}
};
``````

Count Primes

Ugly Number II

https://leetcode.com/problems/perfect-squares/

https://leetcode.com/problems/perfect-squares/discuss/71505/Simple-Java-DP-Solution

https://leetcode.com/problems/perfect-squares/discuss/71512/Static-DP-C%2B%2B-12-ms-Python-172-ms-Ruby-384-ms

https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation