Python DP accepted: the secret to fix the Python TLE error!


  • 4
    N

    I just submitted a simple bottom-up DP solution in python and got a TLE. I searched through the discussions and saw many other people are struggling with TLE for their python code.

    After struggling with my code a little bit, I finally figure out the issue.
    Note that in my accepted code below, my dp array is declared as a class variable. However, if you uncomment the init function to turn it to an instance variable, then you get the TLE error. Thus it is pretty obvious that the test script is written in a bad way where a different instance is created every time a new number is tested.

    So try to get your TLE'ed version of Python code, turn your dp array into a class variable, and try it again. It should be accepted. Note that you do not need any of the simple optimizations I made below to get the code accepted.

    To the Admin of the site: Please fix the test script!

    class Solution(object):
        
        """
        # making the dp array an instance variable would cause TLE
        def __init__(self):
            self.dp = [0]
        """
            
        dp = [0] # so now dp is a class variable
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            for i in range(len(self.dp), n+1):
                result = sys.maxsize
                k = int(math.sqrt(i))
                if k * k == i:
                    self.dp.append(1)
                    continue
                for j in range(1, int(math.sqrt(i)) + 1):
                    result = min(result, self.dp[i - j * j] + 1)
                    if result is 2:
                        break
                self.dp.append(result)
            return self.dp[n]
    

  • 0
    This post is deleted!

  • 0
    V

    why do you use len(self.dp) in "for i in range(len(self.dp), n+1): "? If i use "for i in range(1, n + 1):", it will be wrong. Is there any difference between len(self.dp) and 1? I think the initial len(self.dp) equals 1.


  • 0
    N

    @Volauvent

    It is initially 1. But it's incremental.
    So if you called it with 10, then your dp will be filled up to n is 10, and next time if you call with 100, the len(dp) will be 11, not 1.


  • 0

    @newman2 said in Python DP accepted: the secret to fix the Python TLE error!:

    To the Admin of the site: Please fix the test script!

    There's nothing to fix. It's perfectly fine. It's just not what you'd for some reason like it to be.


Log in to reply
 

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