:-: 4.4 完全平方数 ***** **题干** 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: ``` 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. ``` 示例 2: ``` 输入: n = 13 输出: 2 解释: 13 = 4 + 9. ``` **题目分析：** 该题目可以用四平方和定理求解，也可动态规划求解，也可以当作最短路径来处理。 **新手有可能遇到的解题思路陷阱：** 陷入了贪心做法不可自拔，这道题不能使用贪心来求解，比如12用贪心求解12 = 9 + 1 + 1 +1，其实应该是12 = 4 + 4 + 4。不知道四平方和定理以及不知道由四平方和定理推导出的各个推导，和小技巧。 **解题思路分析以及代码实现：** 第一种思路：四平方和定理： [四平方和定理——维基百科](https://zh.wikipedia.org/wiki/%E5%9B%9B%E5%B9%B3%E6%96%B9%E5%92%8C%E5%AE%9A%E7%90%86) [Lagrange 四平方和定理](https://www.changhai.org/articles/science/mathematics/four_square_theorem.php) 任何一个正整数都可以表示成不超过四个整数的平方之和。也就是说我们的返回值是[1,2,3,4]中的一个值。首先我们看两个得到导论：1.一个数如果含有因子4，我们可以将这个数除以4，用此所得数求并不影响结果，比如2和8或3和12等等，它们的结果相同；2.一个数除以8余7的话，则这个数由4个完全平方数组成。证明：满足此类的数由4个完全平方数组成 [不能写成3个平方数之和的正整数 ](https://bbs.emath.ac.cn/thread-3063-1-1.html) [n＝(8k+7)4^m（k,m 为非负整数）不能表示为三个平方数之和](http://www.mathchina.net/dvbbs/dv_rss.asp?s=xhtml&boardid=7&id=2798&page=51) [欧拉定理，费马小定理、Lagrange定理](http://www.cis.umac.mo/~fstitl/10mmo/sum-4squares.html) 第一种思路代码： ``` 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 = (int) Math.sqrt(n - a * a); if (a * a + b * b == n) { if (a == 0) { return 1; } return 2; } } return 3; } ``` **复杂度分析：** 时间复杂度：O(sqrt(n))。 空间复杂度：O(1)。 第二种思路：动态规划，首先我们就要找出动态转移方程，我不是大佬，只是个菜鸡，只能用笨方法找规律来总结动态转移方程，我们可以有两种思路： **自顶向下**：首先我们需要知道初始F(n) = n（n = 1 + 1 + 1 +......+ 1），题目中说n是由完全平方数组成的，那么n可以拆分一个完全平方数i^2与n-i^2两部分，然后可以得出n = i^2 + (n - i^2)（**i的取值范围为[1, (int)sqrt(n)]**），F(n) = min(n, 1 + F(n - i^2)) => min(1 + F(n - i^2), 1 + F(n - (i + 1)^2))，然后F(n - i^2)等等再分解，这样的话动态转移方程：**F(n) =min(n, 1 + F(n - i^2)) => min(1 + F(n - i^2), 1 + F(n - (i + 1)^2))**。 **自底向上**：首先我们需要知道初始F(n) = n（n = 1 + 1 + 1 +......+ 1），F(0) = 0，F(1) = min(1, 1 + F(1 - 1^2)) = 1（1可以拆分成1^2 +(1 - 1^2)）, F(2) = min(2, 1 + F(2 - 1^2)) = 2（2可以拆分为1^2 + 2 - 1^2），F(3) = min(3, 1 + F(3 - 1^2)) = 3，F(4) = min(4, 1 + F(4 - 1^2)) = min(1 + F(4 - 1^2, 1 + F(4 - 2^2)) = 1，以此类推，得出状态转移方程为：**F(n) =min(n, 1 + F(n - i^2)) => min(1 + F(n - i^2), 1 + F(n - (i + 1)^2))，i的取值范围为[1, (int)sqrt(n)]**。 第二种思路代码： ~~~ public static int numSquares(int n) { int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { dp[i] = i; int top = (int) Math.sqrt(i); for (int j = 1; j <= top; j++) { dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } return dp[n]; } ~~~ 时间复杂度：O(n*sqrt(n))。 空间复杂度：O(n)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**