Force buckle - 354 Russian Doll envelope problem

First , The width will change Ascending , If the width is the same, the height Descending （ Because you have to find the largest letter package in the same width first ）

then , Then the sorted height , Find the longest increasing subsequence Power button -300. The longest increasing subsequence _Node_Su The blog of -CSDN Blog

For example, original data ：      After the above steps ：

[5,4]                       [2,3]

[6,4]                       [5,4]

[6,7]                       [6,7]

[2,3]                       [6,4]

Finally, the longest increasing subsequence of height ：[2,3]=>[5,4]=>[6,7]

There is a convenient way to implement “ First ” Steps for

envelopes.sort(key=lambda x: (x[0], -x[1]))

key=lambda Is constant ,x[0] Express key Sort ,x[1] Express Key value Sort , The default is ascending

class Solution(object):
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        height = []
        for i in range(0, len(envelopes)):
            height.append(envelopes[i][1])
        res = self.lengthOfLIS(height)
        return res

    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [1] * (len(nums))

        for i in range(0, len(nums)):
            for j in range(0, i):  #  You don't need to find anything better than the current nums[i] Small nums[j], Just look in nums[i] The previous small nums[j] that will do 
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)  #  With the current longer dp[j]+1
        res = 0
        for i in range(0, len(dp)):
            res = max(res, dp[i])
        return res


if __name__ == '__main__':
    envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]]
    Sol = Solution()
    res = Solution.maxEnvelopes(Sol, envelopes)
    print(res)