最长递增子序列相关

最长递增子序列及其变种

300.最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //dp[i]表示以nums[i]结尾的最长递增子序列的长度
        int n=nums.size();
        vector<int> dp(n, 1);

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                //寻找nums[0...j-1]中比nums[i]小的元素
                if(nums[i]>nums[j]){
                    //把nums[i]接在后面，形成长度为dp[j]+1，且以nums[i]为结尾的递增子序列
                    dp[i]=max(dp[i], dp[j]+1);
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};

354.俄罗斯套娃信封问题

这道题目是最长递增子序列的一个变种，相当于在二维平面中找一个最长递增子序列，其长度就是最多能嵌套的信封个数。

思路：先对宽w进行升序排序，如果遇到w相等，则按照高度h降序排序；之后把所有的h作为一个数组，在这个数组上计算最长递增子序列的长度就是答案。

但是此方法：leetcode会超时

class Solution {
public:
    static bool Cmp(vector<int>& a, vector<int>& b){
        if(a[0]==b[0]){
            return a[1]>b[1];
        }
        return a[0]<b[0];
    }
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        //按照 w 升序排列，如果 w 相等，则按照 h 降序排列
        sort(envelopes.begin(), envelopes.end(), Cmp);
        int n=envelopes.size();
        vector<int> nums(n);
        for(int i=0;i<n;i++){
            nums[i]=envelopes[i][1];
        }
        int res = LIS(nums);
        return res;
    }
    //最长递增子序列
    int LIS(vector<int>& nums){
        int n=nums.size();
        vector<int> dp(n, 1);

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[i], dp[j]+1);
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res=max(res, dp[i]);
        }
        return res;
    }
};

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& intervals) {
        //动态规划，最长上升子序列的变形

        //按照第一个值，宽 升序排序
        sort(intervals.begin(), intervals.end());
        int n=intervals.size();
        vector<int> dp(n, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(intervals[i][0]>intervals[j][0] && intervals[i][1] > intervals[j][1])
                 // 如果w, h严格升序，尝试更新dp[i]
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        
        int res=0;
        for(int i=0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};
//leetcode 也会超时

面试题 17.08.马戏团人塔

class Solution {
public:
    int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
        //动态规划
        int n=height.size();
        //将身高和体重一一对应起来
        vector<vector<int>> nums;
        for(int i=0;i<n;i++){
            nums.push_back({height[i], weight[i]});
        }
        
        sort(nums.begin(), nums.end());
        vector<int> dp(n, 1);

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i][0]>nums[j][0] && nums[i][1]>nums[j][1]){
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }

        int res=0;
        for(int i=0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};
//leetcode 会超时

面试题 08.13.堆箱子

class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        int n=box.size();
        sort(box.begin(), box.end());
        //dp[i]表示以第i个结尾的箱子，
        vector<int> dp(n);

        //base case
        for(int i=0;i<n;i++){
            dp[i]=box[i][2];
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(box[i][0]>box[j][0] && box[i][1]>box[j][1] && box[i][2]>box[j][2]){
                    dp[i]=max(dp[i], dp[j]+box[i][2]);
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};