给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3 解释: 12 = 4 + 4 + 4. 示例 2:
输入: n = 13
输出: 2 解释: 13 = 4 + 9.
很多人第一眼看到这个问题，想到的第一种做法就是使用贪心算法，但是对于这个问题是不适用的，例如：
如果贪心来做，12 = 9 + 1 + 1 + 1，所以答案为4了，但是实际答案是3。
Lagrange 四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。
引理 1 (Euler 四平方恒等式)： (a2+b2+c2+d2)(w2+x2+y2+z2) = (aw+bx+cy+dz)2 + (ax-bw-cz+dy)2 + (ay+bz-cw-dx)2 + (az-by+cx-dw)2， 其中 a, b, c, d, w, x, y, z 为任意整数。
引理 2： 如果一个偶数 2n 是两个平方数之和， 那么 n 也是两个平方数之和。
引理 3： 如果 p 是一个奇素数， 则存在正整数 k， 使得 kp = m2+n2+1 (其中 m， n 为整数)。
还有一个重要的推论：
我们可以先判断这个数是否满足，如果是，那就ans=4；
完整代码为
class Solution{ private: int is_square(int n){ int sqrt_n = (int)(sqrt(n)); //强制转换 int i；float f； f=（float）i; return (sqrt_n*sqrt_n == n); } public: int numSquares(int n){ // If n is a perfect square, return 1. if (is_square(n)){ return 1; } // The result is 4 if and only if n can be written in the // form of 4^k*(8*m + 7). Please refer to // Legendre's three-square theorem. while ((n & 3) == 0) {// n%4 == 0 n >>= 2; //左移2位 4^a } if ((n & 7) == 7){ // n%8 == 7 return 4; } // Check whether 2 is the result. int sqrt_n = (int)(sqrt(n)); for (int i = 1; i <= sqrt_n; i++){ if (is_square(n - i*i)){ return 2; } } return 3; //其他是3 } };不过这题用动态规划很容易理解
class Solution{ public: int numSquares(int n) { if (n <= 0) { return 0; } vector<int> cntPerfectSquares(n + 1, INT_MAX); cntPerfectSquares[0] = 0; for (int i = 1; i <= n; i++) { // For each i, it must be the sum of some number (i - j*j) and // a perfect square number (j*j). for (int j = 1; j*j <= i; j++) { cntPerfectSquares[i] = min(cntPerfectSquares[i], cntPerfectSquares[i - j*j] + 1); } } return cntPerfectSquares.back(); } };
