```
class Solution {
public:
int numSquares(int n) {
int srt = (int)sqrt(n);
static int table[35535] = { };
if(table[n] != 0) return table[n];
if(srt * srt == n)
{
table[n] = 1;
return 1;
}
else
{
int result = 1 + numSquares(n - srt * srt);
for(int i = srt - 1; i > 0; i--){
int temp = numSquares(n - i * i) + numSquares(i * i);
if(temp < result) result = temp;
}
table[n] = result;
return result;
}
}
};
```