```
public class Solution {
public static int[] memo;
public int numSquares(int n) {
if(memo == null){
memo = new int[(n * 2) + 1];
}
else if(memo.length <= n){
int[] temp = new int[n * 2];
for(int i = 0; i < memo.length; i++){
temp[i] = memo[i];
}
memo = temp;
}
return leastNumSquares(n);
}
private int leastNumSquares(int n){
if(memo[n] > 0){
return memo[n];
}
if(n == 0){
return 0;
}
double root = Math.sqrt(n);
root = Math.floor(root);
int r = (int)root, min = Integer.MAX_VALUE;
while(r > 0){
int squares = leastNumSquares(n - (r*r)) + 1;
min = squares < min ? squares : min;
r--;
}
memo[n] = min;
return min;
}
}
```

This solution uses memoization and a form of amortized doubling on the memoization array. I could probably combine the private method with the given method, but I am alright with the way it turned out.