0354. 俄罗斯套娃信封问题

0354. 俄罗斯套娃信封问题 #

  • 标签:动态规划、二分查找
  • 难度:困难

题目大意 #

给定一个二维整数数组 envelopes 表示信封,其中 envelopes[i] = [wi, hi],表示第 i 个信封的宽度 wi 和高度 hi。

当一个信封的宽度和高度比另一个信封大时,则小的信封可以放进大信封里,就像俄罗斯套娃一样。

现在要求:计算最多能有多少个信封组成一组「俄罗斯套娃」信封。

注意:不允许旋转信封(也就是说宽高不能互换)。

解题思路 #

如果最多有 k 个信封可以组成「俄罗斯套娃」信封。那么这 k 个信封按照宽高关系排序一定满足:

  • $w_0 < w_1 < … < w_{k-1}$
  • $h_0 < h_1 < … < h_{k-1}$

因为原二维数组是无序的,直接暴力搜素宽高升序序列并不容易。所以我们可以先固定一个维度,将其变为升序状态。再在另一个维度上进行选择。比如固定宽度为升序,则我们的问题就变为了:在高度这一维度下,求解数组的最长递增序列的长度。就变为了经典的「最长递增序列的长度问题」。即 0300. 最长递增子序列

「最长递增序列的长度问题」的思路如下:

动态规划的状态 dp[i] 表示为:以第 i 个数字结尾的前 i 个元素中最长严格递增子序列的长度。

遍历前 i 个数字,0 ≤ j ≤ i

  • nums[j] < nums[i] 时,nums[i] 可以接在 nums[j] 后面,此时以第 i 个数字结尾的最长严格递增子序列长度 + 1,即 dp[i] = dp[j] + 1
  • nums[j] ≥ nums[i] 时,可以直接跳过。

则状态转移方程为:dp[i] = max(dp[i], dp[j] + 1)0 ≤ j ≤ inums[j] < nums[i]

最后再遍历一遍 dp 数组,求出最大值即可。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
        size = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        dp = [1 for _ in range(size)]

        for i in range(size):
            for j in range(i):
                if envelopes[j][1] < envelopes[i][1]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)
本站总访问量  次  |  您是本站第  位访问者