问题
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
例子
given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
分析
- 方法一：静态的动态规划。静态状态表可以在所有case中共有，因此可以大大地提高效率（比一般的动态规划快几十倍）；
- 方法二：数学方法。详见Lagrange's four-square theorem.
- 方法三：bfs.
要点
static dynamic programming
时间复杂度
- 方法一：O(n^2)
- 方法二：O(O^0.5)
空间复杂度
- 方法一：O(n)
- 方法二：O(1)
代码
方法一
class Solution {
public:
int numSquares(int n) {
static vector<int> dp({0});
while (dp.size() <= n) {
int curNumSquares = INT_MAX;
for (int i = 1; i * i <= dp.size(); i++) {
curNumSquares = min(curNumSquares, dp[dp.size() - i * i] + 1);
}
dp.push_back(curNumSquares);
}
return dp[n];
}
};
方法二
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 1 + !!a;
}
return 3;
}
};
