Perfect Squares
题目描述
给出正整数 n， 使用最少的 完全平方数 使得他们的和为 n，并返回个数。
Example:
Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9
参考代码
方法一（四方和定理）：
关于四方和定理和四方和恒等式可以参考链接 [1],[2]。 这里不仅仅使用了四方和定理，还有一些奇淫技巧，可以参考[3]。
class Solution {
public:
/*
* @param n a positive integer
* @return an integer
*/
int numSquares(int n) {
// Write your code here
while (n % 4 == 0) n /= 4;
if (n % 8 == 7) return 4;
for (int i = 0; i * i <= n; ++ i) {
for (int j = 0; j * j + i * i <= n; ++ j) {
if (i * i + j * j == n) {
return (i > 0) + (j > 0);
}
}
}
return 3;
}
};
方法二（动态规划）：
以下为“我为人人”的DP写法，也可以很方便的改写成“人人为我”的写法。 这里使用DP的弊端就是 n 不能太大，不仅是时间复杂度，空间复杂度也是 O(n)。
class Solution {
public:
/**
* @param n a positive integer
* @return an integer
*/
int numSquares(int n) {
// Write your code here
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[n];
}
};
LintCode相关题目
- Ugly number II
参考链接： [1]:https://zh.wikipedia.org/wiki/%E5%9B%9B%E5%B9%B3%E6%96%B9%E5%92%8C%E5%AE%9A%E7%90%86