题目：

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：

        数学方式的解法：基于四平方和理论（Lagrange’s four-square theorem）， 每个正整数均可表示为4个整数的平方和。 

         1. 如果整数包含因子4， 可以去掉不影响结果；

         2. 如果除8余7的话， 肯定是由四个完全平方数组成；

         3.  之后按照两个数的平方和拆解整数， 其中！！逻辑取反判断是否正整数还是0， 正整数！！后为1， 0！！后为0；    

         4. 其他情况结果返回3.

int numSquares(int n){
    while(n%4==0){
        n = n/4;
    }
    if (n%8 == 7 ){
        return 4;
    }
    for (int a=0;a*a<n;a++){
        int b = sqrt(n-a*a);
        if (a*a + b*b == n){
            return !!a+!!b;
        }
    }
    return 3;
}

int is_square(int n){
    int sqrt_n = sqrt(n);
    return (sqrt_n*sqrt_n == n);
}
int numSquares(int n){
    if (is_square(n)){
       return 1;
    }   
    while(n%4==0){
        n = n/4;
    }
    if (n%8 == 7 ){
        return 4;
    }
    for (int a=0;a*a<n;a++){
        if (is_square(n-a*a)){
           return 2;
        }
   }
    return 3;
}

时间复杂度O(N)

解题2：

        动态规划的解法：square[i] 表示正整数i能少能由多个完全平方数组成，对于每一个i， 必须是一个数字i-j*j和一个完全平方和j*j的和

class Solution 
{
public:
    int numSquares(int n) {
        if (n <= 0){
            return 0;
        }
        vector<int> square(n+1, INT_MAX);
        square[0] = 0;
        for (int i=1; i<=n; i++){
            for (int j=1; j*j<=i;j++){
                square[i] = min( square[i] ,  square[i-j*j] + 1 );
            }
        }
        return square[n];
    }
};

时间复杂度O(N*N)

解题3：

        广度优先BFS的解法:

1. 设置perfectSquares包含所有平方和小于n的完全平方和，cntPerfectSquares[i-1]记录最少多少个完全平方和的sum可以达到i；
2. 如果perfectSquares最后一个数等于n，返回1；
3. 创建查询队列，将perfectSquares插入队列；
4. 由于perfectSquares存放平方和信息，计数currCntPerfectSquares =1，
5. currCntPerfectSquares +1， 弹出队列，与所有perfectSquares中的完全平方和组合， 如果刚好等于N返回currCntPerfectSquares；
6. 如果当前弹出的完全平方和与对应的perfectSquares中的完全平方和小于n， 并且对应的cntPerfectSquares记录为-，更新记录为currCntPerfectSquares，并放入队列，下一个循环继续处理
7. 如果当前弹出的完全平方和与对应的perfectSquares中的完全平方和大于n，跳出，进行下一次队列弹出，再与perfectSquares匹配。

  class Solution {
public:
    int numSquares(int n) {
        if (n<=0){
            return 0;
        }
        
        vector<int> perfectSquares;
        vector<int> cntPerfectSquares(n+1, 0);
        queue<int> searchQ;
        for (int i = 1; i*i <= n; i++)
        {
            int m= i*i;
            perfectSquares.push_back(m);
            cntPerfectSquares[m-1] = 1;
            searchQ.push(m);
            
        }
        
        if (perfectSquares.back() == n)
        {
            return 1;
        }
        
        int currCntPerfectSquares = 1;
        while (!searchQ.empty())
        {
            currCntPerfectSquares++;
            int searchQSize = searchQ.size();
            
            for (int i=0; i<searchQSize; i++){
               
                int tmp = searchQ.front();
                
                for (auto& j: perfectSquares){
                    if (tmp +j == n){
                        return currCntPerfectSquares;
                    }
                    else if ((tmp+j<n) && cntPerfectSquares[tmp+j-1] == 0){
                        cntPerfectSquares[tmp+j-1] = currCntPerfectSquares;
                        searchQ.push(tmp+j);
                    }
                    else if(tmp +j >n){
                        break;
                    }
                }
                searchQ.pop();
            }
        }
        return 0;
    }
};
时间复杂度O(N*N)

参考

[LeetCode] 279. Perfect Squares 完全平方数

[Leetcode] #279 Perfect Squares (BFS, DP)

Summary of 4 different solutions (BFS, DP, static DP and mathematics)