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.