I know you guys have figured out different DP, DFS, static DP ways for this solution.

Here I just want to share my easiest BFS solution

```
public int numSquares(int n) {
if (n <= 0) return 0;
Queue<Integer> queue = new LinkedList<>();
HashSet<Integer> set = new HashSet<>();
queue.offer(n);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int j = 0; j < size; j++) {
int curr = queue.poll();
int ceiling = (int)Math.pow(curr, 0.5);
if (ceiling * ceiling == curr) return res;
for (int i = ceiling; i > 0; i--) {
if (set.add(curr - i * i)) { //avoid duplicate calculation
queue.offer(curr - i * i);
}
}
}
level++;
}
return res;
}
```