CareerCup

Dynamic programming..

int num_squares(int n){
    int table[n+1];
    int max = floor(sqrt(n));
    int squared;

    for (int i=0; i<=n; i++){
        table[i] = i;
    }
    for (int i=2; i<=max; i++){
        for (int j=0; j<=n; j++){
            squared = pow(i,2);
            if (squared <= j)
                table[j] = min(table[j], table[j-squared]+1);
        }
    }
    return table[n];
}

// Dynamic Programming
using System.IO;
using System;

class Program
{
    static void Main()
    {
        Console.WriteLine("Hello, World!");
        int val = 12;
        int[] table = new int[val+1];
        table[0] = 0;
        
        for ( int i=1; i<=val; i++){
            int maxsqrt = (int) Math.Sqrt(i);
            int localmin = i;
            for (int j=1; j<=maxsqrt; j++){
                if ( table[i-j*j] < localmin) {
                    localmin = table[i-j*j];
                }
            }
            table[i] = localmin + 1;
    }
        
        Console.WriteLine("Min Val:"+ table[val]);
    }
}

dont you mean "return 3" in the second example?

Greedy approach should work. Find the largest perfect square number s that is <= n. Apply the same to the difference (n - s). We can find s by taking square root of n as a float, and then truncating the result downward to the nearest integer.

Greedy approach will not solve this problem

n=12 (3^2+1^2+1^2+1^2) takes 4 summation

Problem should be solved by using dynamic programming.

public static void main(String[] args){
        int n = 12;
        System.out.println("Ans: "+findSolution(n,0));
    }

    private static int  findSolution(int n, int count){
        int sqrt = (int) Math.sqrt(n);
        if((n!=0) && (sqrt*sqrt <= n)){
            System.out.print(sqrt+" ");
            count++;
            count = findSolution(n-(sqrt*sqrt),count);
        }
        return count;
    }

int leastSquares_helper(int n, int max, unordered_map<int, int>* myMap) {
   unordered_map<int,int>::const_iterator got = myMap->find(n);
   if(got != myMap->end()) {
      return got->second;
   }
   int largest = (int)sqrt(n);
   if((largest * largest) == n) {
      myMap->insert(pair<int,int>(n, 1));
      return 1;
   }
   if(largest > max) {
      largest = max;
   }
   int best = INT_MAX;

   while ((largest * largest) > (n/best)) {
      best = min(leastSquares_helper(n - (largest * largest), largest, myMap) + 1, best);
      largest--;
   }
   myMap->insert(pair<int,int>(n, best));
   return best;
}

int leastSquares(int n) {
   unordered_map<int, int>* myMap = new unordered_map<int, int>;
   return leastSquares_helper(n, INT_MAX, myMap);
}


int main(){

   cout<<leastSquares(12);

   getchar();
   return 0;

}

As stated above, the solution is a Dynamic Programming algorithm.

The opt for this looks like:

OPT(value, root):
    if value - (root^2) == 0 return 1
    if value - (root^2) < 0 return INF
    else return 1 + min(OPT(value - (root^2), k) for all k <= root)

We return INF if less than 0 to prevent overshoots from being counted.
Use of memoization is also helpful, having a cache which maps combinations of (value, root) to their calculated values will greatly improve our runtime.

In python, a quick mock up of this looks like

INFIN = 999999

memo = {}

def count_sqr_vals(val):
    max_root = int(pow(val, 0.5))
    return min([rec_search(val, x) for x in range(max_root, 0, -1)])

def rec_search(val, curr):
    if memo.get((val,curr)):
        return memo.get((val,curr))
    if val - (curr**2) < 0:
        memo[(val,curr)] = INFIN
        return INFIN
    if val - (curr**2) == 0:
        memo[(val,curr)] = 1
        return 1
    min_val = min([rec_search(val - (curr**2), x) for x in range(curr, 0, -1)])
    memo[(val,curr)] = 1 + min_val
    return 1 + min_val

Bruteforce

def num_squares(n):
    max = int(n**.5)
    mincount = None
    answer = []
    for r in range(max,0,-1):
        z = n
        p = r
        count = 0
        temp = []
        while z > 0:
            sq = p**2
            if z - sq < 0:
                p -= 1
                continue
            else:
                z -= sq
                count += 1
                temp.append(p)
            if mincount and count > mincount:
                break

            if z == 0:
                if not mincount or count < mincount:
                    mincount = count
                    answer = temp

    return (answer, mincount)

void LeastSquares(int num, std::vector<int>& best, std::vector<int>& curSeq = std::vector<int>(), int cur = 0)
{
   if (!cur)
      cur = (int)sqrtf((float)num);
   if (!num && (!best.size() || (curSeq.size() < best.size())))
   {
      best = curSeq;
      return;
   }
   if (best.size() && curSeq.size() >= best.size())
      return;
   for (; cur > 0; cur--)
   {
      if (num >= cur*cur)
      {
         curSeq.push_back(cur*cur);
         LeastSquares(num - cur*cur, best, curSeq, cur);
         curSeq.pop_back();
      }
   }
}

void main()
{
   int num;
   while (1)
   {
      std::cout << "Enter num\n";
      std::cin >> num;
      std::vector<int> result;
      LeastSquares(num, result);
      std::cout << result.size() << ": (";
      for (int i = 0; i < result.size(); i++)
         std::cout << result[i] << ((i == result.size()-1) ? "" : " + ");
      std::cout << ")\n";
   }
}

output:

Enter num
12
3: (4 + 4 + 4)
Enter num
6
3: (4 + 1 + 1)
Enter num
66
3: (64 + 1 + 1)
Enter num
666
2: (441 + 225)
Enter num
6666
3: (6241 + 400 + 25)
Enter num
66666
3: (66049 + 361 + 256)

def least_perfect_sqr_num(n):
    if n == 1:
        return 1

    sqrts = []
    total = []
    for num in reversed(range(2, n + 1)):
        if not num % math.sqrt(num):
            sqrts.append(num)

    if not sqrts:
        return n
    else:
        for sqrt_no in sqrts:
            total.append(1 + least_perfect_sqr_num(n - sqrt_no))

    return min(total)

dynamic programming

public int findMin (int d){
		int to = (int) Math.sqrt(d) ;
		int []f = new int[d + 1];
		for (int i = 1 ; i <= d ; ++i) {
			f[i] = i ;
		  for (int j = 1 ; j <= to ; ++j) {
		      if (i >= j * j) {
		    	f[i] = f[i - j * j] + 1 < f[i] ? f[i - j * j] + 1 : f[i] ;	
		      }
		  }
		}		
		return f[d];
	}

class CountSquares
{
    public static boolean isSquare(int n)
    {
        return Math.ceil(Math.sqrt(n)) == Math.floor(Math.sqrt(n));
    }

    public static int countSquaresNaive(int n)
    {
        if (n <= 1) {
            return n;
        }

        int minCount = Integer.MAX_VALUE;

        for (int i=n; i>=1; i--) {
            if (isSquare(i)) {
                int c = 1 + countSquaresNaive(n - i);
                if (c < minCount) {
                    minCount = c;
                }
            }
        }

        return minCount;
    }

    public static int countSquaresDP(int n)
    {
        if (n <= 1) {
            return n;
        }

        int[] L = new int[n+1];
        for (int i=0; i<L.length; i++) {
            L[i] = 0;
        }
        L[0] = 0;
        L[1] = 1;

        for (int i=2; i<=n; i++) {
            if (isSquare(i)) {
                L[i] = 1;
            } else {
                int minCount = Integer.MAX_VALUE;
                int k = i / 2;
                for (int j=i-1; j>=k; j--) {
                    minCount = Math.min(minCount, L[j] + L[i-j]);
                    if (minCount <= 2) {
                        break;
                    }
                }
                L[i] = minCount;
            }
        }

        return L[n];
    }

    public static void main(String[] args)
    {
        for (int i=0; i<=50; i++) {
            int a = countSquaresNaive(i);
            int b = countSquaresDP(i);
            assert a == b;
            System.out.println("countSquaresNaive("+i+") = "+a+", countSquaresDP("+i+") = "+b);
        }  
    }
}

Based on BFS search

typedef std::pair<unsigned,unsigned> numDepth;
std::queue<numDepth> q;
hash_set<unsigned> visited;

bool perfectSqrt(unsigned n)
{
 unsigned r = floor(sqrt(n));
 return ( n == r*r);
}


unsigned minSqrtSum(unsigned n)
{
if  ( perfectSqrt(n) ) { return 1;}
 q.push(std::make_pair(n,0));
assert(n >0);
 while (true)
{
 numDepth next = q.front();
 q.pop();
 unsigned r = floor(sqrt(next.first));
 for (unsigned  k = r; k>0; --k)
  {
  unsigned m = n - k*k;
 if (visited.count(m) } continue;
 if ( perfectSqrt(m) ) return next.second+2;
  q.push(std::make_pair(m,next.second+1));
 visited.insert(m);
 }
}
}

import java.util.*;

class Program2{
	int[] min;

	Program2(){
		min = new int[13];
		Arrays.fill(min, Integer.MAX_VALUE);
	}
	public void findMin(int n){
		min[0] = 0;
		for(int i=1 ; i<=n ; i++){
			for(int j=1 ; j*j<=i ; j++){
				min[i] = Math.min(min[i], min[i - j*j] + 1);
			}
		}
	}

	public static void main(String[] args){
		Program2 obj = new Program2();

		obj.findMin(12);
		System.out.println("Min Value: " + obj.min[12]);
	}
}

int number = 45345345;
		int sum = 0;
		//int numCont = 0;
		List<Integer> nums = new ArrayList<Integer>();
		
		int num1 = number;
		while(sum < number) {			
			double n = Math.floor(Math.sqrt(num1));
			int square = (int) (n*n);
			sum += square;
			if (sum == number) {
				nums.add((int) n);
				break;
			} else {
				nums.add((int) n);
				num1 = number - sum;
			}
		}
		
		System.out.println(nums);
		System.out.println(nums.size());

Dynamic programming. Here's an iterative bottom-up approach using memoization:

import math

def perfect_squares(n):
    squares = [x * x for x in range(1, int(math.floor(math.sqrt(n)) + 1))]
    counts = [x for x in range(0, n+1)]

    for i in range(1, n+1):
        for j in squares:
            counts[i] = min(counts[i], 1 + counts[i-j])

    return counts[n]

int solve(int n){

    int minimumSquares[100];
    for(int i=0;i<=n;++i)
        minimumSquares[i] = i; /// i = 1^2 + .... + 1^2


    for(int i=1;i<=n;++i)
        for(int j=1;j*j<=i;++j)
            if( minimumSquares[i] > 1 + minimumSquares[i - j*j])
                    minimumSquares[i] = 1 + minimumSquares[i - j*j];
    return minimumSquares[n];

}

Dynamic programming

The key fact is:
S[i] = min(S[i-1^2] +1, S[i-2^2] +1, + S[i-3^2] +1... )

I took the top-down approach but the bottom up approach works as well.

#python
import math

def nsquares(num, mem):
    if num in mem:
        return mem[num]

    vals = [nsquares(num - (i * i), mem)+1 for i in range(1, int(math.sqrt(num)) + 1)]
    mem[num] = min(vals)
    return mem[num]


print nsquares(7, {0 : 0, 1 : 1} ) #3 --> 7-4 = 3; 3-1 = 2; 2-1 = 1; 1-1 = 0

int f(int n) {
  if (n < 4} return n;
  auto s1 = int(sqrt(n)), s0 = s1-1;
  s1 *= s1; s0 *= s0;
  return min(n/s1 + f(n%s1), 1 + f(n-s0));
}

public int numOfSquares(int n)
	{
		if(n==0) return 0;
		int[] arr = new int[n];

		int count = 1;
		for(int i=0; i<n; i++)
		{
			if(isPerfectSquare(i+1))
				count = 0;
			count ++;
			arr[i] = count;
		}

		int maxNum = (int)Math.sqrt(n);
		for(int a= 0; a<n; a++)
		{
			for(int i=1; i<=maxNum; i++)
			{
				int squared = (int) Math.pow(i, 2);
				if ( a + squared >= n) 
					break;
				int curMin = arr[a + squared];
				if(arr[a] + 1 < curMin)
				{
					arr[a + squared] = arr[a] + 1;
				}
			}
		}

		return arr[n-1];
	}

	private boolean isPerfectSquare(int num)
	{
		int sqrtInt = (int) Math.sqrt(num);
		return sqrtInt*sqrtInt == num;
	}

public int calculateSquares(int n)
{
if(n<0){return -1;}

HashMap<Integer, Integer> leastSquaredmap = new HashMap();
map.put(0,1);
map.put(1,1);
return calculateSquaresHelper(n, map);
}

public int calculateSquaresHelper(int n, HashMap<Integer, Integer> map)
{
if(map!=null && map.contains(n))
{
return map.get(n);
}

//number is a perfect square
if(Math.sqrt(n) % 1 ==0)
{
map.put(n,1);
}

int min = Math.INT_MAX;
for(int i=1; i<=n; i++)
{
int j=n-i;
int minI = calculateSquaresHelper(i,map);
int minJ = calculateSquaresHelper(j,map);
if(minI+minJ < min)
{
min = minI+minJ;
}
}
map.put(n, min);
return min;
}

int num_of_squares(int n) {
	if (n == 0)
		return 0;
	if (n ==1)
		return 1;
	// find the floor of square root of n
	int x = (int)Math.sqrt(n);
	// find what is left in n after subtracting square of x
	int rem = n - (int)Math.pow(x, 2);
	// Answer would be square of x plus num_of_squares(rem)
	return 1+num_of_squares(rem);
}

public static int num_of_squares(int n) {
		if (n==0)
			return 0;
		if (n==1)
			return 1;
		int x = (int) Math.sqrt(n);
		int rem = n - (int)Math.pow(x, 2);
		return 1+num_of_squares(rem);
	}

public static int num_of_squares(int n) {
if (n==0)
return 0;
if (n==1)
return 1;
int x = (int) Math.sqrt(n);
int rem = n - (int)Math.pow(x, 2);
return 1+num_of_squares(rem);
}

public static int num_of_squares(int n) {
		if (n==0)
			return 0;
		if (n==1)
			return 1;
		int x = (int) Math.sqrt(n);
		int rem = n - (int)Math.pow(x, 2);
		return 1+num_of_squares(rem);

}

int

{9}

There is a duplicate question a while ago. The number is no more than 4.
Follow this link to find out the previous question and one solution: cpluspluslearning-petert.blogspot.co.uk/2015/02/dynamic-programming-minimize-number-of.html.

A dynamic solution is provided as well.

what about tweak the question a little bit. The number is a total. In you hands, you have some coins and each coin values at 1, 4, 9, 16, 25 ... n^2 that less than the number. Try to use the least amount of coin to sum up your total.

what about tweak the question a little bit. The number is a total. In you hands, you have some coins and each coin values at 1, 4, 9, 16, 25 ... n^2 that less than the number. Try to use the least amount of coin to sum up your total.

check my explanation and solution:
allenlipeng47.com/PersonalPage/index/view/164/nkey

Using dynamic programming with recursion.

int min = Integer.MAX_VALUE ;
	
	public void squareSum(int rem, int numsq) {
		if( rem == 0 ) {
			if( numsq < min ) 
				min = numsq;
		}
		else if( rem > 0 ) {
			for( int i=1; i <= Math.sqrt(rem); i++) {
				squareSum( rem-(int)Math.pow(i,2), numsq+1);
			}
		}
	}

#include<iostream>
using namespace std;

bool isSquare(int num, int& whose)
{
    int i=2;
    if(num==1)
    {
        whose = 1;
        return true;
    }    
    while(true)
    {
        if(i*i == num)
        {
            whose = i;
            return true;
        }
        else if(i*i  > num)
        {
            return false;
        }
        i++;
    }
}

int main()
{
    int num;
    cout<<"  Get Number :- ";
    cin>>num;
    
    int minTill = num;
    int minV = 0;
    int count;
    int x = 0;
    if(isSquare(num, x))
    {
        minV = 1;
        minTill = 1;
    }
    if(num==3)
    {
        minV = 3;
        minTill = 1;
    }

    while(minTill > 2)
    {
        bool check = false;
        count = 0;
        int diff = num;
        int sum = 0;
    
        for(int i=num;i>0;i--)
        {
            int t = 0;
            if(isSquare(i, t))
            {
                if(minTill == t && check)
                {
                    sum += t*t;
                    i = num-sum;
                    diff = diff-t*t;
                    count++;
                }
                else if(t==1)
                {
                    count = count+diff;
                    i = 0;
                }
                else if(t<minTill)
                {
                    if(!check)
                    {
                        minTill = t;
                        check = true;
                    }
                    sum += t*t;
                    i = num-sum;
                    diff = diff-t*t;
                    count++;
                }
                if(i==4 || i == 1)
                {
                    count++;
                    i = 0;
                }
            }
            if(i==0)
            {
                diff = num;
                sum = 0;
                check = false;
            }
        }
        if(count == 2)
        {
            minV = 2;
            break;
        }
        if(!minV)
            minV = count;
        else if(minV > count && !check)
            minV = count;
        cout<<endl<<endl;
    }
    cout<<"  Result is :- "<<minV<<endl;
    return 0;
}

import math

table = {}

def perfect_square(number):
    if number == 0:
        return 0
    
    sqrt = int(math.sqrt(number))
    minimal = 100
    
    for i in xrange(1, sqrt + 1):
        calc = pow(i, i)
        if number - calc >= 0:
            if (number - calc) not in table:
                table[number - calc] = perfect_square(number - calc) + 1
            
            if table[number - calc] < minimal:
                minimal = table[number - calc]
        
            
    return minimal
print perfect_square(100)

public class SquareSumSvc
{
	public static int findNumSquareTerms(int n)throws InvalidInputException
	{
		if(n<0)
		{
			throw new InvalidInputException();
		}
		int[] sumTermCounts=new int[n+1];
		for(int i=0;i<=n;i++)
		{
			int sqrProd=i*i;
			if(sqrProd<=n)
			{
				sumTermCounts[sqrProd]=1;//if i is a perfect square we only need 1 term.
			}else
			{
				for(int j=0;j*j<=i;j++)
				{
					sumTermCounts[i]=Math.min(sumTermCounts[i],(sumTermCounts[j*j]+sumTermCounts[i-(j*j)]));
				}
			}
		}
		return sumTermCounts[n];
		}
	public static void main(String[] args)
	{
		int n=5;//expecting 2.
		System.out.println(assertEquals(2,findNumSquareTerms(n,2)));
		n=6;//expecting 3.
		System.out.println(assertEquals(2,findNumSquareTerms(n,3)));
		
	}
}

bool sqrtTry(double number, vector<double> v, int tries) {
	if (tries == 1) {
		if (floor(sqrt(number)) == ceil(sqrt(number))) {
			v.push_back(sqrt(number));
			for (int i = 0; i < v.size(); i++)
				cout << v[i] << " ";
			cout << endl;
			return true;
		}
		return false;
	}
	else {
		for (int i = 1; i <= number; i++) {
			if (number - i * i > 0) {
				vector<double> cpy = v;
				cpy.push_back(i);
				if (sqrtTry(number - i * i, cpy, tries - 1))
					return true;
			}	
		}
		return false;
	}
}
uint32_t _tmain()
{
	vector<double> v;
	bool succes = false;
	int tries = 1;
	while (!succes){
		succes = sqrtTry(61, v, tries);
		tries++;
	}
	return 0;
}

//Lagrange's four-square theorem (Bachet's conjecture)
    
    int numSquares(int n) {
        int root = sqrt(n);
        if(root*root==n)
            return 1;   //1 case handeled
        while(n%4==0)
            n/=4;
        if(n%8==7)  //Thanks to Legendre 1798
            return 4;   //Four case handeled
        int i = root;
        while(i*i>0){
            int residue = n-(i*i);
            int residue_root = sqrt(residue);
            if(residue_root*residue_root == residue)
                return 2;
            i--;
        }
        return 3;
    }

}

//Lagrange's four-square theorem (Bachet's conjecture)
    
    int numSquares(int n) {
        int root = sqrt(n);
        if(root*root==n)
            return 1;   //1 case handeled
        while(n%4==0)
            n/=4;
        if(n%8==7)  //Thanks to Legendre 1798
            return 4;   //Four case handeled
        int i = root;
        while(i*i>0){
            int residue = n-(i*i);
            int residue_root = sqrt(residue);
            if(residue_root*residue_root == residue)
                return 2;
            i--;
        }
        return 3;

}

//Lagrange's four-square theorem (Bachet's conjecture)

int numSquares(int n) {
int root = sqrt(n);
if(root*root==n)
return 1; //1 case handeled
while(n%4==0)
n/=4;
if(n%8==7) //Thanks to Legendre 1798
return 4; //Four case handeled
int i = root;
while(i*i>0){
int residue = n-(i*i);
int residue_root = sqrt(residue);
if(residue_root*residue_root == residue)
return 2;
i--;
}
return 3;
}

//Lagrange's four-square theorem (Bachet's conjecture)
    
    int numSquares(int n) {
        int root = sqrt(n);
        if(root*root==n)
            return 1;   //1 case handeled
        while(n%4==0)
            n/=4;
        if(n%8==7)  //Thanks to Legendre 1798
            return 4;   //Four case handeled
        int i = root;
        while(i*i>0){
            int residue = n-(i*i);
            int residue_root = sqrt(residue);
            if(residue_root*residue_root == residue)
                return 2;
            i--;
        }
        return 3;
    }

//Lagrange's four-square theorem (Bachet's conjecture)
    
    int numSquares(int n) {
        int root = sqrt(n);
        if(root*root==n)
            return 1;   //1 case handeled
        while(n%4==0)
            n/=4;
        if(n%8==7)  //Thanks to Legendre 1798
            return 4;   //Four case handeled
        int i = root;
        while(i*i>0){
            int residue = n-(i*i);
            int residue_root = sqrt(residue);
            if(residue_root*residue_root == residue)
                return 2;
            i--;
        }
        return 3;
    }

//Lagrange's four-square theorem (Bachet's conjecture)
    
    int numSquares(int n) {
        int root = sqrt(n);
        if(root*root==n)
            return 1;   //1 case handeled
        while(n%4==0)
            n/=4;
        if(n%8==7)  //Thanks to Legendre 1798
            return 4;   //Four case handeled
        int i = root;
        while(i*i>0){
            int residue = n-(i*i);
            int residue_root = sqrt(residue);
            if(residue_root*residue_root == residue)
                return 2;
            i--;
        }
        return 3;
    }

#include<stdio.h>
#include<math.h>
int A[10000]={0};
int MinSquare(int n)
{
int max=999999;
if(n==0)
{
return 0;
}
int i;
if(A[n]==0)
{
for(i=1;i<=sqrt(n);i++)
{
int x=n-(i*i);
if(x<0)
{
break;
}

int y=1+MinSquare(x);
if(y<=max)
{
max=y;
}
}
A[n]=max;
}
else
{
max=A[n];
}
return max;
}

int main()
{
printf("%d",MinSquare(24));
return 0;
}

#include<stdio.h>
#include<math.h>
int A[10000]={0};
int MinSquare(int n)
{
int max=999999;
if(n==0)
{
return 0;
}
int i;
if(A[n]==0)
{
for(i=1;i<=sqrt(n);i++)
{
int x=n-(i*i);
if(x<0)
{
break;
}

int y=1+MinSquare(x);
if(y<=max)
{
max=y;
}
}
A[n]=max;
}
else
{
max=A[n];
}
return max;
}

int main()
{
printf("%d",MinSquare(24));
return 0;
}

#include<stdio.h>
#include<math.h>
int A[10000]={0};
int MinSquare(int n)
{
	int max=999999;
	if(n==0)
	{
		return 0;
	}
	int i;
	if(A[n]==0)
	{
		for(i=1;i<=sqrt(n);i++)
		{
			int x=n-(i*i);
			if(x<0)
			{
			break;
			}
		
			int y=1+MinSquare(x);
			if(y<=max)
			{
			max=y;
			}	
		}
		A[n]=max;
	}
	else
	{
			max=A[n];
	}	
return max;	
}

int main()
{
    printf("%d",MinSquare(24));
    return 0;
}

#include<stdio.h>
#include<math.h>
int A[10000]={0};
int MinSquare(int n)
{
int max=999999;
if(n==0)
{
return 0;
}
int i;
if(A[n]==0)
{
for(i=1;i<=sqrt(n);i++)
{
int x=n-(i*i);
if(x<0)
{
break;
}

int y=1+MinSquare(x);
if(y<=max)
{
max=y;
}
}
A[n]=max;
}
else
{
max=A[n];
}
return max;
}

int main()
{
printf("%d",MinSquare(24));
return 0;
}

#include<stdio.h>
#include<math.h>
int A[10000]={0};
int MinSquare(int n)
{
int max=999999;
if(n==0)
{
return 0;
}
int i;
if(A[n]==0)
{
for(i=1;i<=sqrt(n);i++)
{
int x=n-(i*i);
if(x<0)
{
break;
}

int y=1+MinSquare(x);
if(y<=max)
{
max=y;
}
}
A[n]=max;
}
else
{
max=A[n];
}
return max;
}

int main()
{
printf("%d",MinSquare(24));
return 0;
}

Its edit of 1-0 Knapsack problem

Formula -

if j < sql[i - 1]
dp[i, j] = dp[i -1, j]
elif sq[i - 1] % j == 0
dp[i, j] = sq[i - 1] / j
else
dp[i, j] = min(dp[i - 1, j], (sq[i - 1] / j) + dp[i - 1, j - sq[i - 1] % j]

def getmin(n):
    dp = dict()
    dp[0] = 0
    dp[1] = 1
    dp[2] = 2
    dp[3] = 3
    for i in range(4,n+1):
        dp[i] = i
        for x in range(1,i+1):
            tmp = x*x
            if tmp > i:
                break
            else:
                dp[i] = min(dp[i], 1+dp[i-tmp])
    res = dp[n]
    del dp
    return res
print "Enter Number"
num = int(raw_input())
print getmin(num)

C++ solution:

#include <iostream>
#include <vector>
#include <cmath>
#include <string>

using uint = unsigned int;
using VectorUInts = std::vector<unsigned int>;

VectorUInts GetLeastPerfectSquares(uint n) {
  if (n == 0) {
    return VectorUInts{};
  }

  VectorUInts minSoFar;

  bool hasMinBeenFound = false;

  uint cachedStartValue = sqrt(n);
  bool isFirstMainLoop = true;
  while(!hasMinBeenFound && cachedStartValue > 0) {
    uint currInt = n;
    bool isFirstLoop = true;
    VectorUInts squares;
    while(currInt > 0) {
      uint newVal = 0;
      if (!isFirstMainLoop && isFirstLoop) {
        newVal = cachedStartValue;
      }
      else {
        newVal = static_cast<uint>(sqrt(static_cast<float>(currInt)));
      }

      if(isFirstLoop) {
        cachedStartValue = (cachedStartValue - 1);
        isFirstLoop = false;
      }

      newVal = newVal * newVal;

      if (newVal > 0) {
        squares.push_back(newVal);
      }
    
      currInt -= newVal;
    }

    if (squares.size() < minSoFar.size() || isFirstMainLoop)  {
      minSoFar = std::move(squares);
      isFirstMainLoop = false;
    }
    else {
      hasMinBeenFound = true;
    }

  }

  return minSoFar;
}

int main (int argc, char **argv) {
  auto leastPerfectSquares = GetLeastPerfectSquares(std::stoul(argv[1]));

  for (const auto &val : leastPerfectSquares) {
    std::cout << val << "\n";
  }

  return 0;
}

Greedy approach should work? Find the largest square number s that's <= given number n. Then apply recursively to (n - s). Since 1 is a square number, we're guaranteed to be reach n.