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

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

Solution 1：Lagrange four square theorem

From Lagrange four square theorem, we can know that any natural number can represented 

by 4 square numbers. So the answer of this problem has been limited to 1~4.

The number can be written in form  

Then the Three square theorem then suggested that any number can satisfy the theorem above can 

also be represented by 3 square numbers.

So the situations can be handled respectively.

class Solution {
public:
    int numSquares(int n) {
        while (n % 4 == 0) 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;
    }
};

Solution 2 : Dynamic programming.

The problem is similar to the Coin change problem.

class Solution {
public:
    int numSquares(int n) {
       

        vector<int> dp(n+1,n+1);
        
        dp[0]=0;
        
        for(int i=1;i<=n;i++)
            for(int j=0;j*j<=n;j++){
                if(j*j<=i)
                    dp[i]=min(dp[i],dp[i-j*j]+1);
            }    
            
        return dp.back();

 

    }
};