保研机试之【动态规划--最长递增子序列】

本文主要是介绍保研机试之【动态规划--最长递增子序列】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一题： 300. 最长递增子序列 - 力扣（LeetCode）

dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> dp(2510,1);int len=nums.size();int res=1;for(int i=0;i<len;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j]){dp[i]=max(dp[i],dp[j]+1);res=max(res,dp[i]);}}}return res;}
};

第二题：354. 俄罗斯套娃信封问题 - 力扣（LeetCode） 

先对envelopes进行排序（cmp函数）

dp[i] 表示以 envelopes[i] 这个元素为结尾的最长递增子序列的长度。

但是这种写法会TLE，列在这里是因为他是最长递增子序列的一个变种。

bool cmp(vector<int>& a,vector<int>& b){if(a[0]<b[0]){return true;}else if(a[0]==b[0]){if(a[1]<=b[1]){return true;}else{return false;}}else{return false;}
}
class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {/*排序*/sort(envelopes.begin(),envelopes.end(),cmp);int len=envelopes.size();int res=1;vector<int> dp(100010,1);for(int i=0;i<len;i++){for(int j=0;j<i;j++){if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){dp[i]=max(dp[i],dp[j]+1);res=max(res,dp[i]);}}}return res;}
};

这篇关于保研机试之【动态规划--最长递增子序列】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---