```
public class Solution {
public int numSquares(int n) {
if(n < 4) return n;
int[] results = new int[n+1];
results[0] = 0;
int cur = 0;
for(int i = 1; i <= n; i++){
if(i == (cur + 1) * (cur + 1)){
results[i] = 1;
cur++;
}else results[i] = 1 + minRes(results, cur, i);
}
return results[n];
}
public int minRes(int[] results, int cur, int i){
int minRes = Integer.MAX_VALUE;
for(int j = 1; j <= cur; j++){
if (results[i - j * j] < minRes) minRes = results[i - j*j];
}
return minRes;
}
}
```