This is recursive only solution, very similar in structure to recursive implementation of coin exchange here

```
int ns(int n, vector<vector<int> > &memo, int i=1)
{
int a, b, c;
if( n ==0 )
return memo[0][i]=0;
if( n < 0 || i*i >n)
return INT_MAX;,
if( memo[n][i] != -2 ) return memo[n][i];
// use i*i
a = ns(n-i*i,memo,i+1);
if( a!=INT_MAX) a+=1;
// use i*i repeatedly.
b = ns(n-i*i,memo,i);
if( b!=INT_MAX) b+=1;
// skip i*i
c = ns(n,memo,i+1);
return memo[n][i]=min(a,min(b,c));
}
```