279. 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.

Thoughts:

1. Dynamic Programming
   1. sq[i] = ... to number i
   2. sq[0] = 0
   3. search from 1 to j (j ^2 <= i): sq[i] = min(sq[i], sq[i-j^2] + 1)
2. Static Dynamic Programming
   1. sq[i]: ... to number i
   2. sq[0] = 0
   3. in the loop, each time push the result for sq[i] into ith of the container.
3. Mathematical Solution
   1. Lagrange's Four Square Theorem: Any natural number can be represented by the sum of at most 4 perfect square numbers
   2. number that need 4 perfect square meets: 4^k(8m + 7)
4. BFS
   1. Each node a number
   2. An edge between i and j exists if from node i to j, there is only one perfect number away.

Code 1:

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

        return sq[n];
    }
};

Code 2:

class Solution {
public:
    int numSquares(int n) {
        if( n <= 0 ) return 0;
        static vector<int> sq ({0});
        while(sq.size() <= n){
            int m = sq.size();
            int cur = INT_MAX;
            for(int i = 1; i * i <= m; i++){
                cur = min(cur, sq[m - i * i] + 1);
            }

            sq.push_back(cur);
        }

        return sq[n];
    }
};

Code 3: Lagrange's Four Square Theorem

class Solution {
private: 
    int is_square (int n){
        int sqrt_n = (int) (sqrt(n));
        return ( sqrt_n * sqrt_n == n);
    }
public:
    int numSquares(int n) {
        // result of 1:
        if(is_square(n)) return 1;

        // Based on Lagrange's Four Square theorem, there 
        // are only 4 possible results: 1, 2, 3, 4.

        // result of 4: 4^k(8m + 7)   https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem
        while((n & 3) == 0) n >>= 2; // n%4 == 0
        if((n & 7) == 7) return 4; // n%8 == 7

        // result of 2:
        int sqrt_n = (int)(sqrt(n));
        for(int i = 1; i <= sqrt_n; i++){
            if(is_square(n - i * i)) return 2;
        }

        return 3;
    }
};

Code 4: BFS: O(n*E)

class Solution {
public:
    int numSquares(int n) {
        if(n <= 0){
            return 0;
        }

        vector<int> perfectSquares;
        vector<int> record (n);

        for(int i = 1; i * i <= n; i++){
            perfectSquares.push_back(i * i);
            record[i * i - 1] = 1;
        }

        if(perfectSquares.back() == n) return 1;

        queue<int> q;
        for(auto& num: perfectSquares){
            q.push(num);
        }

        int count = 1;
        while(!q.empty()){
            count++;
            int size = q.size();
            for(int i = 0; i < size; i++){
                int curNum = q.front();
                for(auto& sqNum: perfectSquares){
                    if(curNum + sqNum == n) return count;
                    else if((curNum + sqNum < n) && (record[curNum + sqNum - 1] == 0)){
                        q.push(curNum + sqNum);
                        record[curNum + sqNum - 1] = 1; //add into the queue, mark as explored
                    }
                    else if( curNum + sqNum > n) break;
                }
                q.pop();
            }
        }

        return 0;

    }
};

from zhukov's post