Python naive O(n^2) DP get TLE


  • 0

    Java and C++ use the same approach passed.

    class Solution(object):
        def maxEnvelopes(self, envelopes):
            if envelopes is None or len(envelopes) == 0:
                return 0
            dp = [1 for _ in xrange(0, len(envelopes))]
            envelopes.sort()
            ret = 1
            dp[0] = 1
            for i in xrange(1, len(envelopes)):
                maxDoll = -1
                for j in reversed(xrange(0, i)):
                    if self.canFit(envelopes[j], envelopes[i]):
                        if dp[j] > maxDoll:
                            maxDoll = dp[j]
                if maxDoll == -1:
                    dp[i] = 1
                else:
                    dp[i] = maxDoll + 1
                ret = max(dp[i], ret)
                
            return ret
                    
                    
        def canFit(self, size1, size2):
            if size1[0] < size2[0] and size1[1] < size2[1]:
                return True
            return False

Log in to reply
 

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