# LeetCode – Perfect Squares
Date: 2019-07-02


# 题目：

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 完全平方数](https://www.cnblogs.com/grandyang/p/4800552.html)

[\[Leetcode\] #279 Perfect Squares (BFS, DP)](https://blog.csdn.net/qq_34264472/article/details/71307917)

[Summary of 4 different solutions (BFS, DP, static DP and mathematics)](https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-\(BFS-DP-static-DP-and-mathematics\))