最长递增子序列相关

最长递增子序列及其变种

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;
    }
};

func lengthOfLIS(nums []int) int {
    //dp[i]表示以nums[i]结尾的最长递增子序列的长度
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    for i := 0; i < n; i++ {
        for 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)
            }
        }
    }
    res := 0
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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;
    }
};

func maxEnvelopes(envelopes [][]int) int {
    //按照 w 升序排列，如果 w 相等，则按照 h 降序排列
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] == envelopes[j][0] {
            return envelopes[i][1] > envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    n := len(envelopes)
    nums := make([]int, n)
    for i := 0; i < n; i++ {
        nums[i] = envelopes[i][1]
    }
    res := LIS(nums)
    return res
}

//最长递增子序列
func LIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

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

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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 也会超时

func maxEnvelopes(intervals [][]int) int {
    //动态规划，最长上升子序列的变形

    //按照第一个值，宽 升序排序
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][0] == intervals[j][0] {
            return intervals[i][1] < intervals[j][1]
        }
        return intervals[i][0] < intervals[j][0]
    })
    n := len(intervals)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    for i := 0; i < n; i++ {
        for 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)
            }
        }
    }
    
    res := 0
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
//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 会超时

func bestSeqAtIndex(height []int, weight []int) int {
    //动态规划
    n := len(height)
    //将身高和体重一一对应起来
    nums := make([][]int, n)
    for i := 0; i < n; i++ {
        nums[i] = []int{height[i], weight[i]}
    }
    
    sort.Slice(nums, func(i, j int) bool {
        if nums[i][0] == nums[j][0] {
            return nums[i][1] < nums[j][1]
        }
        return nums[i][0] < nums[j][0]
    })
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    for i := 0; i < n; i++ {
        for 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)
            }
        }
    }

    res := 0
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
//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;
    }
};

func pileBox(box [][]int) int {
    n := len(box)
    sort.Slice(box, func(i, j int) bool {
        if box[i][0] == box[j][0] {
            if box[i][1] == box[j][1] {
                return box[i][2] < box[j][2]
            }
            return box[i][1] < box[j][1]
        }
        return box[i][0] < box[j][0]
    })
    //dp[i]表示以第i个结尾的箱子，
    dp := make([]int, n)

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

    for i := 0; i < n; i++ {
        for 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])
            }
        }
    }
    res := 0
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}