专栏首页算法修养LeetCode 354 Russian Doll Envelopes (动态规划)

LeetCode 354 Russian Doll Envelopes (动态规划)

题目

一道好题目,把最长递增子序列扩展到二维,但是这道题和最长递增子序列是有区别的,它不要求是序列,只是在数组中找到一组最长的组合,不要求顺序在初始中相同。

这是个二维的最长递增子序列,由于没有顺序限制,所以我们把第一维进行排序,然后对第二维进行动态规划

接下来就和最长递增子序列的思路一样: 效率是O(n^2)的算法,

struct Node
{
    int x;
    int y;
    Node(){}
    Node(int x,int y)
    {
        this->x = x;
        this->y = y;
    }
}a[100005];
int dp[100005];
int compare1(Node a,Node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

int compare2(Node a,Node b)
{
    if(a.x<b.x && a.y<b.y)
        return 1;
    return 0;
}

int pos;
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        
        pos=0;
        for(int i=0;i<envelopes.size();i++)
        {
            a[pos++] = Node(envelopes[i][0],envelopes[i][1]);
        }
        
        sort(a,a+pos,compare1);
        
        int res=0;
        for(int i=0;i<pos;i++)
        {
            dp[i]=1;
            for(int j=i-1;j>=0;j--)
            {
                if(compare2(a[j],a[i]))
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            
            res = max(res,dp[i]);
        }
        return res;
        
    }
};

最长递增序列,还有一种O(nlogn)的解法,这道题目也有同样的解法。 但是这种解法里给第一维排序的时候,第二维也要顺道排一下,在第一维相同的情况,第二维排倒序,然后再去动态规划, 这是因为,根据O(nlogn)的解法,我们需要维护一个第二维的递增数组,在第一维相同的而情况,第二维越小越小,在不断往递增数组里插入的时候,很明显第二维倒序会非常符合题目要求,并且减少很多不必要的判断

struct Node
{
    int x;
    int y;
    Node(){}
    Node(int x,int y)
    {
        this->x = x;
        this->y = y;
    }
}a[100005];
int dp[100005];
int compare(Node a,Node b)
{
    if(a.x==b.x)
        return a.y>b.y;
    return a.x<b.x;
}
int pos;
int len;
int binarySearch(int x)
{
    int l=0;
    int r=len-1;
    
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(x > dp[mid])
        {
            l = mid+1;
        }
        else
        {
            r = mid-1;
        }
    }
    
    return l;
}

int last;
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        
        pos=0;
        for(int i=0;i<envelopes.size();i++)
        {
            a[pos++] = Node(envelopes[i][0],envelopes[i][1]);
        }
        
        sort(a,a+pos,compare);
        return fun();
        
    }
    
    int fun()
    {
        len = 0;
        for(int i=0;i<pos;i++)
        {
            int index = binarySearch(a[i].y);
            dp[index] = a[i].y;
            if(index==len)
                len++;
        }
        return len;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法细节系列(7):354. Russian Doll Envelopes

    在做这道题之前,我们先来看一道它的简化版本300. Longest Increasing Subsequence,官网给出了两种解法,时间复杂度分别为O(n2)...

    用户1147447
  • LeetCode 354. 俄罗斯套娃信封问题(最长上升子序 DP/二分查找)

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

    Michael阿明
  • 动态规划问题-LeetCode 91、72(动态规划方程)

    一条包含字母 A-Z 的消息通过以下方式进行了编码: 'A' -> 1 'B' -> 2 … 'Z' -> 26 给定一个只包含数字的非空字符串,请计算解码方法...

    算法工程师之路
  • Leetcode动态规划模板

    由于面试解题没有时间进行数学验证,因此需要训练一些基本feeling,满足feeling即可果断尝试,十拿九稳!

    SL_World
  • LeetCode 879. 盈利计划(动态规划)

    第 i 种工作会产生 profit[i] 的利润,它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作,就不能参与另一项工作。

    Michael阿明
  • LeetCode 808. 分汤(动态规划)

    当我们把汤分配给某人之后,汤就没有了。 每个回合,我们将从四种概率同为0.25的操作中进行分配选择。 如果汤的剩余量不足以完成某次操作,我们将尽可能分配。 ...

    Michael阿明
  • leetcode-198-House Robber(动态规划)

    You are a professional robber planning to rob houses along a street. Each house ...

    chenjx85
  • LeetCode 97 Interleaving String (动态规划)

    给你三个字符串s1,s2,s3 问你s3是否由s1和s2互相交叉组成。也就是说s3中的某个子序列是s1,剩下的字符串组成s2。

    ShenduCC
  • 程序员面试金典 - 面试题 08.13. 堆箱子(DP)

    堆箱子。给你一堆n个箱子,箱子宽 wi、深 di、高 hi。 箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。 实现一种方法,搭...

    Michael阿明
  • Leetcode | 第5节:排序方法的设计,堆,堆排序,快速排序

    这一节我们来继续讨论排序算法所延伸出的一些题目。如果有空的话,还会说一些堆,也就是优先队列的一些比较经典的题目。

    学弱猹
  • LeetCode 70. 爬楼梯(动态规划)

    题目链接:https://leetcode-cn.com/problems/climbing-stairs/

    Michael阿明
  • LeetCode中级算法-动态规划

    给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

    码农帮派
  • LeetCode 213. House Robber II (动态规划)

    这道题目 https://www.cnblogs.com/dacc123/p/12295924.html 一样,改进了一点,就是首尾也是相邻的。

    ShenduCC
  • LeetCode 837. 新21点(动态规划)

    爱丽丝以 0 分开始,并在她的得分少于 K 分时抽取数字。 抽取时,她从 [1, W] 的范围中随机获得一个整数作为分数进行累计,其中 W 是整数。 每次抽...

    Michael阿明
  • Leetcode | 第一节:动态规划(上)

    从去年7月到现在,我已经在北京的互联网公司呆了整整一年的时间。这中间经历过各种各样的酸甜苦辣,自己为了面试刷题的过程(从杉数到滴滴——未入门算法工程师再找实习工...

    学弱猹
  • Leetcode | 第2节:动态规划(下)

    这一节的题目绝大部分都是选择的Leetcode中的hard(当然也有少部分的medium)。主要是挑选了一些之前看过的高频题。这些题目没有什么通用的解法,每一个...

    学弱猹
  • 动态规划应用--最长递增子序列 LeetCode 300

    有一个数字序列包含n个不同的数字,如何求出这个序列中的最长递增子序列长度?比如2,9,3,6,5,1,7这样一组数字序列,它的最长递增子序列就是2,3,5,7,...

    Michael阿明
  • leetcode-746-Min Cost Climbing Stairs(动态规划)

    chenjx85
  • 不同路径(动态规划)- leetcode 62

    最近在看leetcode的题目,都是面试题,需要面试的同学可以努力刷这里的题目,因为很多公司的面试笔试题都是参考这个上面的。相对OJ上的题目,感...

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券