BFS--Perfect Squares

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

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.
Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

解法1:

 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;  
            }
            if ((n & 7) == 7) // n%8 == 7
            {
                return 4;
            }
            
            // Check whether 2 is the result.
            int sqrt_n = (int)(Math.sqrt(n)); 
            for(int i = 1; i <= sqrt_n; i++)
            {  
                if (is_square(n - i*i)) 
                {
                    return 2;  
                }
            }  
            
            return 3;  
        } 

     private boolean is_square(int i) {
            for (int j = 0; j <i; j++) {
                if(j*j==i){
                    return true;
                }
            }
            return false;
        }

上面核心数学理论：四平方和定理

(a^2 + b^2 + c^2 + d^2)(x^2 + y^2 + z^2 + w^2) = 
(ax + by + cz + dw)^2 + (ay - bx + cw - dz)^2 + (az - bw - cx + dy)^2 + (aw + bz - cy - dx)^2

以及推导出的结论：
1.上面的解，只可能是4个答案：1，2，3，4
2.如果结果是4，则n可以表示为：4^k(8m + 7)

以上算法最快。

解法2:

 public int numSquares(int n) {
            int[] memo = new int[n + 1];
            
            Arrays.fill(memo, Integer.MAX_VALUE);
            memo[0] = 0;
            
            for (int i = 1; i <= n; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 1; i - (j * j) >= 0; j++) {//
                    min = Math.min(min, 1 + memo[i - (j * j)]);
                }
                memo[i] = min;
            }
            
            return memo[n];//      [0, 1, 2, 3, 1, 2, 3, 4, 2]
                           //n=8    [0, 1, 2, 3, 4, 5, 6, 7, 8]
     
        } 

总结：
1）如果n是123456，
解法1只要3ms，
解法2要56ms。
可见数学对科学的重要性。
2）Math.sqrt，获取的是最接近开平方的数。
比如：Math.sqrt(Double.valueOf(13))==3；
3）(n & 3) == 0) // n%4 == 0
((n & 7) == 7) // n%8 == 7
上面两个是恒等的。

其他联想：关于double装箱拆箱的问题见：
https://www.jianshu.com/p/1322a59f9e69