Python weird but not too bad DFS


  • 0
    E

    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.


Log in to reply
 

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