第九章 動態(tài)規(guī)劃part13

300. 最長遞增子序列

給你一個整數(shù)數(shù)組?nums?，找到其中最長嚴(yán)格遞增子序列的長度。

子序列?是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7]?是數(shù)組?[0,3,1,6,2,2,7]?的子序列。

沒有想出來，思維定式在狀態(tài)定義。本題重點(diǎn)是遞推公式：

dp[i]：前i天包含第i天的最長遞增子序列的長度

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

674. 最長連續(xù)遞增序列

給定一個未經(jīng)排序的整數(shù)數(shù)組，找到最長且?連續(xù)遞增的子序列，并返回該序列的長度。

連續(xù)遞增的子序列?可以由兩個下標(biāo)?l?和?r（l < r）確定，如果對于每個?l <= i < r，都有?nums[i] < nums[i + 1]?，那么子序列?[nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]?就是連續(xù)遞增子序列。

?思路與上一題類似

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size(),1);for(int i=1;i<nums.size();i++){if(nums[i]>nums[i-1])  dp[i]=dp[i-1]+1;}int maxLength=0;for(int i=0;i<nums.size();i++){maxLength=max(maxLength,dp[i]);}return maxLength;}
};

718. 最長重復(fù)子數(shù)組

給兩個整數(shù)數(shù)組?nums1?和?nums2?，返回?兩個數(shù)組中?公共的?、長度最長的子數(shù)組的長度?。

dp[i][j]:截止nums1前i個，nums2 前j個存在的最長重復(fù)子數(shù)組的長度。

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size(),vector<int>(nums2.size(),0));for(int j=0;j<nums2.size();j++){if(nums2[j]==nums1[0])  dp[0][j]=1;}for(int i=0;i<nums1.size();i++){if(nums1[i]==nums2[0])  dp[i][0]=1;}for(int i=1;i<nums1.size();i++){for(int j=1;j<nums2.size();j++){if(nums1[i]==nums2[j])  dp[i][j]=dp[i-1][j-1]+1;}}int maxLength=0;for(int i=0;i<nums1.size();i++){for(int j=0;j<nums2.size();j++){maxLength=max(maxLength,dp[i][j]);}}return maxLength;}
};