LeetCode 279. Perfect Squres
DP 是笨办法中的高效办法，又是一道可以被好办法打败的 DP 题。
题目描述
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.
解题思路
这道题是说，给出一个正整数 n，问可以最少用几个完全平方数的加和来表示。
我的第一个思路是 n = a + b (a <b) 然后用 DP 来消除重复计算，结果超时了，因为时间复杂度太高，到了 O(N^2) 级别。
另一个思路好一点，拆成 n = a + k*k 的形式，同样的 DP 算法，时间复杂度只有 O(NlogN)。
其实本题最佳算法可以达到 O(logN)，用到了 Lagrange 四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。这里贴出来源和代码，仅作了解。
参考代码
/*
* @lc app=leetcode id=279 lang=cpp
*
* [279] Perfect Squares
*/
// @lc code=start
class Solution {
public:
/*
int numSquares(int n) {
vector<int> dp(n+1);
dp[1] = 1;
for (int k=2; k<=n; k++) {
int x = sqrt(k);
if (x * x == k) {
dp[k] = 1;
} else {
int res = k; // 1 + 1 + 1 + ...
for (int i = 1; i <= k/2; i++) {
res = min(res, dp[i]+dp[k-i]);
} // split into any a+b
dp[k] = res;
}
}
return dp[n];
} // O(N^2), TLE, 585/588 cases passed
*/
int numSquares(int n) {
vector<int> dp(n+1);
dp[0] = 0;
for (int k=1; k<=n; k++) {
int x = sqrt(k);
if (x * x == k) {
dp[k] = 1;
} else {
int res = k; // 1 + 1 + 1 + ...
for (int i=1; i<=x; i++) {
res = min(res, 1 + dp[k-i*i]);
} // split into i*i+b
dp[k] = res;
}
}
return dp[n];
} // O(NlogN), AC
};
// @lc code=end
O(logN) 数学解法
参考博客 grandyang
前两行代码对算法效率的提升很大，虽然不知道怎么证明这个 ……
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;
}
};