For every integer i, iterate through all perfect square numbers m, from 1 to ~ sqrt(i), find the minimum of fewest[i - m * m] + 1. the i-m*m term is smaller than i such is already computed.
For for n, there are sqrt(n) such perfect numbers. The total runtime is n*sqrt(n), which is n^1.5

. I am not sure about the runtime accuracy. Anyone at good math gives a comment? Also, is there a better solution? Something like O(n) time or better, or O(1) space?

```
public class Solution {
public int numSquares(int n) {
int[] fewest = new int[n + 1];
fewest[0] = 0;
int min;
for (int i = 1; i <= n; i++) {
min = i;
for (int m = 1; m * m <= i; m++) {
min = Math.min(min, 1 + fewest[i - m * m]);
}
fewest[i] = min;
}
return fewest[n];
}
}
```