从此无心爱良夜
任他明月下西楼
C++，dp背包，数学题。
dp（背包问题）
首先想到的就是dp，如果用数组dp来记录n由m个完全平方数组成的话，就是dp[n] = m.
对于数字n，可以进行分解，分解成某个数s和完全平方数的和，于是就有了dp[n] = dp[s] + 1 。
然后我们假设\(dp(n) \)表示数字\(n \)最少可以表示为\(dp(n) \)个完全平方数的和，就能写出状态转移方程：
\[dp(n) = min\{dp(n), dp(n - i * i) + 1\}\]然后就能进入写代码的思路了。
因为上述公式中\(dp(n) \)是基于\(dp(n - i * i) \)才能得到最小值，所以我们需要在从小到大进行遍历，然后逐步拿到最优解。
代码很简短：
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1);
for (int i = 1; i <= n; i++) {
dp[i] = i;
for (int j = 1; j * j <= i; j++)
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
return dp[n];
}
};
数学解法
数学解法是在评论区看到的，也就是有个理论：任何一个数，都可以由小于等于4个的完全平方数相加得到。
然后根据这个理论，有个推论：
当\(n \)满足如下公式时，才只能由4个完全平方数得到, \(a \)和\(b \)为某个整数：
\[n = 4^a (8b + 7)\]否则，就是只能由1-3个完全平方数得到。
由一个完全平方数得到就非常好验证了。。。这个大家都懂，直接开方。。。
由两个完全平方数相加，其实也很好懂，直接从小到大循环，直接看他是不是等于两个完全平方数相加就行了。
也就是：
// 验证1
int m = static_cast<int>(sqrt(n));
// 验证2
if (m * m == n) return 1;
for (int i = 1; i * i <= n; i++) {
int j = static_cast<int>(pow(n - i * i, 0.5));
if (j * j + i * i == n) return 2;
}
那由三个完全平方数相加怎么验证呢？ 排除上述三种不就是了？？？？
所以就很容易写出代码了：
class Solution {
public:
int numSquares(int n) {
// 验证1
int m = static_cast<int>(sqrt(n));
// 验证2
if (m * m == n) return 1;
for (int i = 1; i * i <= n; i++) {
int j = static_cast<int>(pow(n - i * i, 0.5));
if (j * j + i * i == n) return 2;
}
// 验证4
while (n % 4 == 0) n /= 4;
if (n % 8 == 7) return 4;
return 3;
}
};
