```
//AC - 144ms - DP method;
int numSquares(int n)
{
int *mins = (int*)malloc(sizeof(int)*(n+1)); //store the minimal number of the PerfectSquare;
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.

```
//using static feature to avoid redundant searching;
int helper(int n)
{
static int mins[1000000] = {0};
static int i = 1;
for(; i <= n; i++)
{
int min = INT_MAX;
int square = 1;
if(mins[i]) continue;
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 - 4ms;
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 >>= 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;
}
```