LeetCode刷题实战354：俄罗斯套娃信封问题
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 俄罗斯套娃信封问题，我们先来看题面：
https://leetcode-cn.com/problems/russian-doll-envelopes/
You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.
One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.
Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).
Note: You cannot rotate an envelope.
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1
解题
https://blog.csdn.net/qq_35683407/article/details/114373289
这是一道经典的 DP 模型题目：最长上升子序列（LIS）。
首先我们先对 envelopes 进行排序，确保信封是从小到大进行排序。
问题就转化为我们从这个序列中选择 k 个信封形成新的序列，使得新序列中的每个信封都能严格覆盖前面的信封（宽高都严格大于）。
我们可以定义状态 f[i] 为考虑前 i 个物品，并以第 i 个物品为结尾的最大值。
对于每个 f[i] 而言，最小值为 1，代表只选择自己一个信封。
那么对于一般的 f[i] 该如何求解呢？因为第 i 件物品是必须选择的。我们可以枚举前面的 i - 1 件物品，哪一件可以作为第 i 件物品的上一件物品。
在前 i - 1 件物品中只要有符合条件的，我们就使用 max(f[i], f[j] + 1) 更新 f[i]。
然后在所有方案中取一个 max 即是答案。
// 354maxEnvelopes.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
//按照特定规则排序
struct rule
{
public:
bool operator()(const vector<int>& e1, const vector<int>& e2)
{
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
}
};
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
if (envelopes.size() == 0)return 0;
int maxvalue = 0;
sort(envelopes.begin(), envelopes.end(), rule());//第一个元素排序
vector<int>dp(envelopes.size() + 1,1);
//第二个元素按照最长递增子序列LIS
for (int i = 0; i < envelopes.size(); i++)
{
for (int j = 0; j < i; j++)
{
if (envelopes[i][1]>envelopes[j][1])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
if (dp[i] > maxvalue)maxvalue = dp[i];
}
return maxvalue;
}
};
int main()
{
Solution s;
vector<vector<int>> envelopes = { {4, 5},{4, 6},{6, 7},{2, 3},{1, 1} };
cout << s.maxEnvelopes(envelopes) << endl;
std::cout << "Hello World!\n";
}
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
上期推文：
