Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

&nbsp;
Example 1:

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


Example 2:

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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 104


class Solution:

    def __init__(self):
        self.perSq = []

    def numSquares(self, n):
        # finding perfect squares up to n
        i = 1
        while i*i <= n:
            self.perSq.append(i*i)
            i += 1

        return self.lengths(n)

    # algorithm to find sum from perfect squares
    def outcomes(self, n, current):
        rem = n
        nums = []
        while sum(nums) != n:
            if current < len(self.perSq)*-1:
                current = self.perSq[0]

            val = self.perSq[current]

            if rem < val:
                current -= 1
                continue
            else:
                nums.append(val)
                rem -= val
                if (rem > 0) and (rem % val == 0):
                    nums.append(val)
                    rem -= val

        return len(nums)

    # algorithm to find sum with least possible numbers
    def lengths(self, n):
        data = []
        for i in range(-1, -1*(len(self.perSq)+1), -1):
            data.append(self.outcomes(n, i))

        return min(data)
class Solution {
    public int numSquares(int n) {
        
        ArrayList<Integer> perfect_squares = new ArrayList<>();
        int i=1;
        while(i*i <= n){
            perfect_squares.add(i*i);
            i++;
        }
        Integer[][] dp = new Integer[n+1][perfect_squares.size()+1];
        int answer = helper(n , perfect_squares , perfect_squares.size()-1,dp);
        return answer;
    }
    
    public int helper(int n , ArrayList<Integer> coins ,int i,Integer[][] dp){
        
        if(n == 0){
            return 0;
        }
        if(i<0){
            return 999999;      //  I'm not taking INT_MAX here, since int variables will overflow with (1 + INT_MAX)
			                             // just take any number greater than constraint ( 10^4) 
        }
        if(dp[n][i] != null){
            return dp[n][i];
        }
        int nottake = 0 + helper(n , coins, i-1,dp);
        int take = 9999999;
        if(coins.get(i) <= n){
            take = 1 + helper(n-coins.get(i),coins,i,dp );          
        }
        dp[n][i] = Math.min(nottake,take);
        return dp[n][i];
        
        
        
    }
    
    
}
class Solution {
public:
    int numSquares(int n) {
        
        vector<int> perfectSq;
        
        for(int i = 1; i*i <= n; ++i){
            perfectSq.push_back(i*i);
        }
        
        int m = perfectSq.size();
        vector<vector<int>> dp( m+1, vector<int>(n+1, 0));
        
        dp[0][0] = 0;
        for( int i = 1; i <= n; ++i ) dp[0][i] = INT_MAX;
        
        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                
                if( j < perfectSq[i-1]){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = min( dp[i-1][j], dp[i][ j - perfectSq[i-1] ] + 1);
                }
                
            }
        }
   
        return dp[m][n];
    }
};
var numSquares = function(n) {
    let dp = new Array(n+1).fill(Infinity);
    
    dp[0] = 0;
    
    for(let i=1; i <= n; i++){
        for(let k=1; k*k <= i; k++){
            dp[i] = Math.min(dp[i],dp[i - (k*k)] + 1);
        }
    }
    
    return dp[n];
};
Perfect Squares