问题：

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

解决：

① 给定一个正整数，求它最少能由几个完全平方数组成。本解法找到一个规律。

【四平方和定理】任意一个正整数均可表示为4个以内的平方数之和。

class Solution { //2ms

    public int numSquares(int n) {         while(n % 4 == 0) n /= 4;         if (n % 8 == 7) return 4;         for (int i = 0;i * i <= n;i ++){             int j = (int) Math.sqrt(n - i * i);             if (i * i + j * j == n){                 return (i > 0 && j > 0) ? 2 : 1;             }         }         return 3;     } }

② 递归方法。遍历所有比n小的完全平方数，然后对n与完全平方数的差值递归调用函数，目的是不断更新最终结果，直到找到最小的那个。

class Solution { //326ms

    public int numSquares(int n) {         int count = n;         int num = 2;         while(num * num <= n){             int a = n / (num * num);             int b = n % (num * num);             count = Math.min(count,a + numSquares(b));             num ++;         }         return count;     } }

③ 动态规划。如果一个数x可以表示为一个任意数a加上一个平方数bｘb，也就是x=a+bｘb，那么能组成这个数x最少的平方数个数，就是能组成a最少的平方数个数加上1（因为b*b已经是平方数了）。时间 O(N^2) ，空间 O(N)。

class Solution { //64ms

    public int numSquares(int n) {         int[] dp = new int[n + 1];         Arrays.fill(dp, Integer.MAX_VALUE);//将所有非平方数的结果置为最大，保证之后比较的时候不被选中         for (int i = 0;i * i <= n;i ++){//将所有平方数的结果置为1             dp[i * i] = 1;         }         for (int i = 0;i <= n;i ++){//从小到大找任意数i             for (int j = 0; i + j * j <= n;j ++){//从小到大找平方数j*j                 dp[i + j * j] = Math.min(dp[i] + 1,dp[i + j * j]);             }         }         return dp[n];     } }