# Two DP solutions enclosed with a mathematical one in C, well-commented

• ``````//AC - 144ms - DP method;
int numSquares(int n)
{
int *mins = (int*)malloc(sizeof(int)*(n+1)); //store the minimal number of the PerfectSquare;
mins[0] = 0;
for(int i = 1; i <= n; i++)
{
int min = INT_MAX;
int square = 1;
for(int r=1; square <= i; r++) //traverse the previous result to get the min;
{
int t = mins[i-square]+1;
min = t < min? t : min;
square = r*r;
}
mins[i] = min;
}
return mins[n];
}
``````

Another DP solution but optimised further to avoid redundant operation by static feature in C.

``````int helper(int n)
{
static int mins[1000000]; //using static feature to avoid redundant searching;
mins[0] = 0;
for(int i = 1; i <= n; i++)
{
int min = INT_MAX;
int square = 1;
for(int r=1; square <= i; r++)
{
int t = mins[i-square]+1;
min = t < min? t : min;
square = r*r;
}
mins[i] = min;
}
return mins[n];
}

//AC - 124ms;
int numSquares(int n)
{
return helper(n);
}
``````

``````//AC - 4ms - mathematical method;
int numSquares(int n)
{
//Based on Lagrange's Four Square theorem, there
//are only 4 possible results: 1, 2, 3, 4.
//The result is 4 if and only if n can be written in the form of 4^k*(8*m + 7).
while(n%4 == 0) //(n & 3) == 0
n >>= 2;
if(n%8 == 7)
return 4;
for(int a=0; a*a <= n; ++a) //consider 1 and 2;
{
int b = sqrt(n-a*a);
if(a*a + b*b == n)
return 1+!!a; //if a==0, then return 1 otherwise return 2;
}
return 3;
}``````

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