[354][困难][贪心][动态规划] 俄罗斯套娃信封问题

题目描述

354. 俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明: 不允许旋转信封。

示例:

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

解题思路

贪心

俄罗斯套娃信封问题

将[300][中等][贪心][二分][动态规划][树状数组] 最长上升子序列从一维扩展到二维. 假设每个信封表示为(w, h), 分别代表宽度和高度.

首先对w进行排序, 这样我们对h求最大上升子序列就可以了, 这样对应的二维子序列, 无论宽度还是高度都是上升序列, 从而将二维问题简化为一维问题.

还有一个问题需要注意, 与[300][中等][贪心][二分][动态规划][树状数组] 最长上升子序列不同, 其中会出现相等的数值, 但相同的宽度或高度是不能套娃的, 这会导致, 例如[[1，3]，[1，4]，[1，5]，[2，3]]这种已经按w排序好的数组, 求h的最大子序列得到[3，4，5], 但实际是塞不进去的.

使用一个技巧, 排序的使用以w为主序, 以h为辅, 且h倒序排列. 这样当w相等的几个数组排列在一起, 对应的h是倒序的, 不会组成递增序列, 上面数组的排序变为[[1，5]，[1，4]，[1，3]，[2，3]], 上面的问题也就解决了.

也就是说当后面的h大于前面的h时, 两者对应的w肯定不会相等, 而w是排序过的, 因此前者是能被后者套娃的.

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        length = []
        for _, height in envelopes:
            index = bisect.bisect_left(length, height)
            if index == len(length):
                length.append(height)
            else:
                length[index] = height
        return len(length)

动态规划

同理, 只是对h的求解变成了动态规划的方法.

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        if n == 0:
            return 0
        envelopes.sort(key=lambda x: (x[0], -x[1]))

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