Recursive-only approach

  • 0

    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));

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.