```
public int numSquares(int n) {
if (n <= 0)
return 0;
int[] dp = new int[n + 1];
dp[1] = 1;
// j is index between 1 and i; l = j*j; l+r=i.
int l = 1, j = 1, r = n - 1, min = n, root = 0;
for (int i = 2; i <= n; i++) {
root = (int) Math.sqrt(i);
if (root * root == i) {
dp[i] = 1;
} else {
j = 1; l = 1; r = i - 1; min = n;
while (r > 0) {
min = Math.min(min, dp[l] + dp[r]);
j++;
l = j * j;
r = i - l;
}
dp[i] = min;
}
}
return dp[n];
}
```