【LeetCode】动态规划—354. 俄罗斯套娃信封问题（附完整Python/C++代码）

动态规划—354. 俄罗斯套娃信封问题

• 前言介绍
• 题目描述
• 基本思路
  • 1. 问题定义
  • 2. 理解问题和递推关系
  • • 2.1 降维思路：
    • 2.2 动态规划递推关系：
    • 2.3 优化方法：二分查找
    • 伪代码：
  • 3. 解决方法
  • • 3.1 排序 + 动态规划
    • 3.2 排序 + 二分查找
  • 4. 进一步优化
  • 5. 小总结
• Python代码
• • • Python代码解释总结：
• C++代码
• • • C++代码解释总结：
• 总结

前言介绍

俄罗斯套娃信封问题 是一个二维优化问题，类似于经典的 最长递增子序列（LIS） 问题。给定若干个信封，每个信封具有两个维度：宽度 w 和高度 h。要求找出最多可以嵌套的信封个数。一个信封 A 可以嵌套到信封 B 中的条件是：A.w < B.w 且 A.h < B.h。

通过将问题从二维降到一维，并结合动态规划和二分查找的思想，我们可以有效地解决这个问题。本文将详细讲解这一思路，并提供 Python 和 C++ 的实现。

题目描述

在这里插入图片描述

基本思路

1. 问题定义

给定一组信封，每个信封具有宽度 w 和高度 h。要求找到最多可以嵌套的信封个数。信封 A 可以嵌套在信封 B 中的条件是：

这个问题可以理解为一个二维的优化问题，通过某种方式排序或优化后，问题可以简化为经典的一维 最长递增子序列（LIS） 问题。

2. 理解问题和递推关系

2.1 降维思路：

我们可以通过 排序 将问题从二维降到一维：

1. 首先，我们可以按照信封的宽度 w 进行升序排序。
2. 其次，如果两个信封的宽度相同，我们需要按照高度 h 降序排序。这样做可以确保同宽度的信封不会被错误地嵌套。
3. 最后，只需要在排序后的高度 h 上寻找 最长递增子序列（LIS）。

2.2 动态规划递推关系：

在已经排序的信封序列中，问题变成了在信封高度 h 上寻找最长递增子序列。定义 dp[i] 为以信封 i 结尾的最长嵌套序列的长度。对于每个信封 i，我们可以通过前面的信封来更新 dp[i]：

其中 envelope_j.h 和 envelope_i.h 分别是信封 j 和 i 的高度。

2.3 优化方法：二分查找

我们可以将动态规划求解 LIS 的时间复杂度优化为 O(n log n)，通过二分查找来维护一个数组 dp，该数组动态记录了当前找到的最长递增子序列：

1. 使用二分查找在 dp 数组中找到信封的高度 h 应插入的位置。
2. 如果 h 可以替换 dp 数组中的某个元素，就进行替换，否则将 h 追加到 dp 数组末尾。
3. 最终 dp 数组的长度即为最长递增子序列的长度。

伪代码：

sort envelopes by width ascending and by height descending if width is the same
initialize dp array for LIS on heights
for each envelope in envelopes:
    perform LIS on heights using dynamic programming or binary search
return length of the longest increasing subsequence in heights

3. 解决方法

3.1 排序 + 动态规划

1. 排序信封：
   • 首先按宽度 w 升序排序，若宽度相同则按高度 h 降序排序。
2. 动态规划：
   • 只需考虑信封的高度 h，问题变为 LIS 问题，使用 dp 数组维护最长递增子序列。

3.2 排序 + 二分查找

• 通过二分查找可以将 LIS 的时间复杂度从 O(n^2) 优化为 O(n log n)。
• 使用 bisect_left（Python）或 lower_bound（C++）来找到合适的位置并更新 dp 数组。

4. 进一步优化

通过结合二分查找的方式，时间复杂度可以优化为 O(n log n)，适用于大规模数据。

5. 小总结

• 该问题的关键是通过排序将问题简化为 LIS，从而降维为一维的递增序列问题。
• 使用二分查找来进一步优化 LIS 的求解过程，能够在 O(n log n) 时间内找到最优解。

以上就是俄罗斯套娃信封问题问题的基本思路。

Python代码

class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        # 先对信封按宽度升序排序；如果宽度相同，则按高度降序排序
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        # 只需要在高度数组上寻找LIS
        heights = [envelope[1] for envelope in envelopes]
        
        # tails数组用于存储LIS
        dp = []
        
        for h in heights:
            idx = bisect_left(dp, h)  # 找到 h 在dp中应插入的位置
            if idx < len(dp):
                dp[idx] = h  # 替换当前位置的值
            else:
                dp.append(h)  # 如果找不到合适的位置，直接追加
         
        return len(dp)  # dp数组的长度即为最长递增子序列的长度

Python代码解释总结：

1. 排序：信封按照宽度升序排序，若宽度相同则按高度降序排序，以保证不会出现错误的嵌套。
2. LIS 求解：使用 bisect_left 在 dp 数组中找到当前高度 h 应插入的位置，并动态维护 dp 数组。
3. 返回结果：dp 数组的长度即为最长递增子序列的长度。

C++代码

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        // 对信封进行排序，宽度升序排列，宽度相同时高度降序排列
        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
        });

        // 提取高度
        vector<int> heights;
        for (const auto& envelope : envelopes) {
            heights.push_back(envelope[1]);
        }

        // 使用动态规划+二分查找计算LIS
        vector<int> dp;
        for (int h : heights) {
            auto it = lower_bound(dp.begin(), dp.end(), h);  // 找到h应该插入的位置
            if (it != dp.end()) {
                *it = h;  // 替换当前值
            } else {
                dp.push_back(h);  // 如果没有合适的位置，追加h
            }
        }

        return dp.size();  // dp数组的长度即为最长递增子序列的长度
    }
};

C++代码解释总结：

1. 排序：信封按照宽度升序排列，若宽度相同则按高度降序排列，确保不会错误嵌套。
2. LIS 求解：通过 lower_bound 查找应插入 dp 数组中的位置，动态维护 dp 数组，记录最长递增子序列的长度。
3. 返回结果：最终 dp 数组的长度即为最大嵌套信封的数量。

总结

• 关键思想：本问题的核心在于通过排序将二维问题降维为一维问题，从而将信封嵌套转化为 最长递增子序列（LIS）问题。
• 优化方式：通过 二分查找 来优化 LIS 的求解过程，时间复杂度从 O(n^2) 优化到 O(n log n)，从而可以高效处理大规模数据。
• 实用性：这种降维思想适用于很多其他类型的二维优化问题，比如二维版本的 LIS 问题，通过排序和降维思想可以大大简化问题的求解。