leetcode354. 俄罗斯套娃信封问题

思路：因为不允许相同宽度或者长度的信封嵌套，所以可以先对长度进行升序排序，长度相同对宽度进行降序排序
之后再根据宽度计算最长子序列，这样就避免了相同的宽度或者长度嵌套。
最后就是经典的计算最长子序列的方法了

def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        if not envelopes:
            return 0
        
        envelopes.sort(key = lambda x: (x[0],-x[-1]))

        n = len(envelopes)
        stack = [-1]
        res = 0
        for i in range(n):
            if envelopes[i][1] > stack[-1]:
                stack.append(envelopes[i][1])
            else:
                index = bisect.bisect_left(stack,envelopes[i][1])
                stack[index] = envelopes[i][1]
        return len(stack) - 1

动态规划计算最长子序列，超时

def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        if not envelopes:
            return 0
        
        envelopes.sort(key = lambda x: (x[0],-x[-1]))

        n = len(envelopes)
        dp = [1]*n 
        for i in range(n):
            for j in range(i):
                if envelopes[i][1] > envelopes[j][1]:
                    dp[i] = max(dp[i],dp[j]+1)
        res = 0
        for i in range(n):
            res = max(dp[i],res)
        return res