方法一： 动态规划
https://segmentfault.com/a/1190000003768736
https://siddontang.gitbooks.io/leetcode-solution/content/dynamic_programming/perfect_squares.html
复杂度
时间 O(N^2) 空间 O(N)
思路
如果一个数x可以表示为一个任意数a加上一个平方数bｘb，也就是x=a+bｘb，那么能组成这个数x最少的平方数个数，就是能组成a最少的平方数个数加上1（因为b*b已经是平方数了）。
public class Solution { /** * @param n a positive integer * @return an integer */ public int numSquares(int n) { // Write your code here int[] dp = new int[n + 1]; // 将所有非平方数的结果置最大，保证之后比较的时候不被选中 Arrays.fill(dp, Integer.MAX_VALUE); // 将所有平方数的结果置1 for (int i = 0; i * i <= n; i++) { dp[i * i] = 1; } // 从小到大找任意数a for (int i = 0; i <= n; i++) { // 从小到大找平方数bｘb for (int j = 1; i + j * j <= n; j++) { // 因为a+b*b可能本身就是平方数，所以我们要取两个中较小的 dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j]); } } return dp[n]; } }
方法二：
数学 四平方和定理
https://www.cnblogs.com/grandyang/p/4800552.html
时间 O(N^2) 空间 O(N)
如果一个数x可以表示为一个任意数a加上一个平方数bｘb，也就是x=a+bｘb，那么能组成这个数x最少的平方数个数，就是能组成a最少的平方数个数加上1（因为b*b已经是平方数了）。
原文：http://www.cnblogs.com/codingEskimo/p/6903068.html