Python weird but not too bad DFS

  • 0

    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:
            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:

    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.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.