Why is Python DP solution TLE


  • 8
    Z

    I made these two lists static however still TLE

       class Solution(object):
            def numSquares(self, n):
                """
                :type n: int
                :rtype: int
                """
                self.dp = [i for i in range(n+1)]
                self.squares = [i*i for i in range(1, int(n**0.5) + 1)]
                
                for i in range(1, n+1):
                    for sq in self.squares:
                        if i - sq < 0:
                            break 
                        self.dp[i] = min(self.dp[i], self.dp[i - sq] + 1)
                        
                return self.dp[-1]

  • 0
    L

    Good question. The same solution in Java beats 91%.


  • 0
    D

    I tried with DP algorithm but get very poor performance (5%), the same algorithm beats 99% in "Ugly Number II" which is a quite similar problem.


  • 0
    L

    My code is about twice speed as yours, but stil TLE, sigh

        def numSquares(self, n): 
            """ 
            :type n: int
            :rtype: int
            """
            if math.sqrt(n) == int(math.sqrt(n)):
                return 1
    
            l = map(lambda i : i*i, [i for i in range(1, int(math.sqrt(n)))])
            f = [ 0 for i in range(n+1) ]
    
            i = 1 
            while i < n+1:
                f[i] = min([ f[i-j] for j in l if i - j >= 0 ]) + 1 
                i += 1
    
            return f[n]
    

  • 0
    W

    Because Python is slow, which forces you to find a better algorithm. Or, you can use other languages to AC.


  • 0
    S

    Initializing self.dp and self.squares are actually O(n), while n can be very large.


  • 0

    @zkh1991 I have the same question


  • 0
    T

    @zkh1991 Replace the if statement by if i < sq


  • 0

    @zkh1991
    DP solution can be accepted, my code is 99% the same as your but only process a corner case at the very beginning , not very good performance but still beats 1/3 of the solutions on average:

        if n == int(n**0.5):
            return 1
        dp = [i for i in xrange(n+1)]
        square = [i**2 for i in xrange(int(n**0.5)+1)]
        for i in xrange(1,n+1):
            for item in square:
                if i-item<0:
                    break
                else:
                    dp[i] = min(dp[i],dp[i-item]+1)
       return dp[n]
    

Log in to reply
 

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