LeetCode300——Longest Increasing Subsequence-蒲公英云

LeetCode300——Longest Increasing Subsequence

青旅半醒 2022-08-09 19:30 177阅读 0赞

LeetCode300——Longest Increasing Subsequence

题意：

最长上升子串，LIS问题，经典的动态规划问题。据说有用到二分的方法，这个还没有仔细研究，先说说朴素的方法：

动归方程可以如下描述：

dp[i] 表示以 nums[i]结尾的最长上升子串的长度。

为了得到dp[i]，我们首先要找出最大的dp[j] 其中 j 的范围是 [0,i-1]

当nums[i] > nums[j]时，dp[i]=上述最大值加1。

代码：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0 || nums.size() == 1)
            return nums.size();
        vector< int >dp(nums.size());//init
        int result=0;
        dp[0] = 1;
        for (int i = 1; i < nums.size(); i++)
        {
            int maxNum = 0;
            for (int j = 0; j < i; j++)
            {
                if (dp[j]>maxNum&&nums[j]<nums[i])
                {
                    maxNum = dp[j];
                }
            }
            dp[i] = maxNum+1;
            result = dp[i] > result ? dp[i] : result;
        }
        return result;
    }
};

-————————————————-2015年11月15日更新-————————————————

看了July的算法视频，发现了一种新的方法。。。

先对原序列进行排序生成新的有序序列 nums2

再对nums和nums2做LCS（最长公共子序列）运算。

之后测试后会补齐代码。

-————————————————-2017年2月5日更新-————————————————

时隔一年多，学会了用LCS解决LIS的算法，不过在LeetCode上出现Memory Limit错误

方法很简单，就是先将原序列排序，去重，在对这两个序列做LCS算法。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int>copied_nums(nums.begin(),nums.end());
        sort(copied_nums.begin(),copied_nums.end());
        copied_nums.erase(unique(copied_nums.begin(),copied_nums.end()),copied_nums.end());
        int m=nums.size();
        int n=copied_nums.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1));
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(nums[i]==copied_nums[j])
                {
                    dp[i+1][j+1]=dp[i][j]+1;
                }
                else
                {
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        return dp[m][n];
    }
};