I have read the DP, BFS, and Math solutions, but I went through the discussion and didn't see DFS as the mainstream solution, so just sharing for your interest.

'''

```
def numSquares(self, n):
self.r = sys.maxint
self.n = n
return self.recursion(n, int(n ** 0.5), 0)
def recursion(self, n, s, prev_num):
if n == 0:
return 0
res = sys.maxint
for i in range(s, 0, -1):
i_square = i ** 2
num, rest = n / i_square, n % i_square
if num + prev_num > self.r:
break
res = min(res, num + self.recursion(rest, int(rest ** 0.5), prev_num + num))
if n == self.n:
self.r = min(self.r, res)
return res
```

'''

My idea is simple:

For n, i start with sqrt(n), and do a DFS on n % (i ** 2).

At the beginning, I got TLE without (Of course)

'''

```
if num + cur_num > self.r:
break
```

'''

Then I just added the restriction, if DFS goes more steps than the current minimum result, stop.

I know the math solution's performance beats this dummy's ass off, but I am just sharing it for your reference.

It is not too bad though, beating 70%, around 400 ms for Python.

And there are lots of room to make improvement, like the for loop doesn't necessarily need to go to 0, etc.