leetcode354. 俄罗斯套娃信封问题
发布时间
阅读量：
阅读量
题目链接：[力扣
请在LeetCode上解决俄罗斯套娃问题
题意：
给定一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] 表示第 i 个信封的宽度和高度。
如果存在另一个信封其宽度和高度均大于当前信封的尺寸，则当前信封可以被放入其中。
不允许对任何信封进行翻转或旋转处理。
请确定最大的嵌套数量。
方法： 动态规划，序列DP
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(),envelopes.end());//将信封从小到大排序
int size = envelopes.size();
vector<int> dp(size,1);//动态规划向量，dp[i]表示以i结尾的序列的最大长度
int maxL = 1;
for(int i=1;i<size;i++)
{
for(int j=0;j<i;j++)
{
if(envelopes[j][0]<envelopes[i][0]&&envelopes[j][1]<envelopes[i][1])
{
dp[i] = max(dp[i],dp[j]+1);
}
}
maxL = max(dp[i],maxL);
}
return maxL;
}
};
代码解释全部评论 (0)
还没有任何评论哟~