```
public int numSquares(int n) {
int[] opt = new int[n+1];
opt[1] = 1;
for(int i = 2; i <= n; i++){
int min= i;
for(int m = 1; m * m <= i; m++){
if(m * m == i){
opt[i] = 1;
break;
}
}
if(opt[i] != 1){
for(int j = 1; j <= (i/2); j++){
min = Math.min(min, opt[j] + opt[i-j]);
opt[i] = min;
}
}
}
return opt[n];
}
```