#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int function(int n)
{
    if (n == 1)
        return 1;
    else
        if (n == 0)
        return 0;
    else{

        int k = 999999999;
        for (int i = 1; i <= sqrt(n); i++)
        {
            int a = function(n - i*i);
            if (a < k )
                k = min(k, a);
        }
        return function(k) + 1;



    }


}

int main()
{
    int n;
    cin >> n;
    cout << function(n) << endl;

}

use memoization

Thank you Noob, I got an AC with your help.

One optimization No need to start loop from always from 1 , sqrt(N)/2 is enough ;) thing why?. :)