1.300最長遞增子序列

1.問題描述

找到其中最長嚴格遞增子序列的長度。

子序列?是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。

2.問題轉換

從nums[0...i]的最長的遞增的子序列

3.解題思路

1. 每一個位置的nums[i]都有兩種狀態：是否放入
2. 對于放入狀態：找到從[0..j](j<i)之間的遞增子序列，如果滿足遞增，放入子序列中，找到其中最長的那個遞增子序列，更新長度。
3. 對于不放入狀態：如果不滿足遞增，則不放入。

4.為什么使用動態規劃？

因為從[0..i]的最長的遞增子序列狀態一定是由[0..j]的狀態遞推出來，所以考慮使用動態規劃的方法。

5.動態規劃的具體實現

1. dp[j]數組的含義：代表的是從nums[0..j]的最長遞增子序列。
2. 遞推公式：for(int i = 0;i<j;i++){? ? ? ? if(nums[j]>nums[i]){//首先需要滿足遞增? ? ? ? ? ? ? ? ? ? dp[j] = max(dp[j],dp[i]+1);//從中選擇最長的作為最長遞增子序列.dp[i] +1:其中i可以等效為背包問題里面的j-weight[i],1可以等效為背包問題里面的value[i].? ? ? ? ? ? ? }? ? ? ? ? }
3. 初始化：默認情況下每個的都是1，因為自身可以當做唯一的那一個遞增子序列。
4. 遍歷順序：由遞推公式可以知道，應該是滿足從小到大的方式進行遍歷。

6.進階：使用動態規劃和二分法來解決

1.思路

我們使用一個數組tail用來存放從[0..i]的單調遞增數組的尾數（而且對應的nums[i]越小越好），tail[i]代表的是尾數，i代表的是長度。

2.具體實現

1.遍歷數組得到此時的nums[i],根據nums[i]在tail數組中找到能夠滿足的最左側的位置。

2.最左側的位置的查找：使用二分法來找到滿足嚴格遞增的最長的長度。可能會出現兩種情況：

? ? ? ? 1.left<res(即在tails的范圍內)當tails[mid]<nums[i],tails[left]>nums[i]:此時將tails[left] = nums[i],可以保證在后面運行的時候能夠盡可能的找到更長的長度。

? ? ? ? 2.當left == res（即這個數比最右側的那個遞增的都長）。此時res++;tails[left] = nums[i].

3.最后的返回值就是對應的一個res的長度。

class Solution {
public:int lengthOfLIS(vector<int>& nums) {/*//方法1：動態規劃int n = nums.size();vector<int> dp(n,1);//dp[j]:從0-j數組的最長的遞增子序列int result = 1;for(int j = 1;j<n;j++){for(int i = 0;i<j;i++){if(nums[j]>nums[i]){dp[j] = max(dp[j],dp[i]+1);}}if(result<dp[j])result = dp[j];}return result;*///方法2：動態規劃+二分查找int n = nums.size();vector<int> tails(n,0);//用來存放一個單調遞增的數組的尾數int res = 0;//代表的是單調遞增的最大長度for(auto num:nums){//用于在tail數組中找到需要替換的那個位置tails[i]<num<tails[i+1],此時將其替換為tails[i+1] = num;//如果這個值在這個里面找不到，就放在最右邊,同時res++;int left = 0,right = res;while(left<right){//[left,right)循環不變量int mid = left +(right - left)/2;if(tails[mid]<num)left = mid+1;else right = mid;}tails[left] = num;if(res == right) res++;}return res;}
};

2.647最長連續遞增子序列

1.問題描述

找到其中最長連續遞增子序列的長度。

2.問題轉換

從nums[0...i]的最長的連續遞增的子序列

3.解題思路

1. 每一個位置的nums[i]都有兩種狀態：是否放入
2. 對于放入狀態：nums[i]>nums[i-1],則放入。
3. 對于不放入狀態：如果不滿足遞增，則不放入。

4.為什么使用動態規劃？

因為從[0..i]的最長的遞增子序列狀態一定是由前一個的狀態遞推出來，所以考慮使用動態規劃的方法。

5.動態規劃的具體實現

1. dp[j]數組的含義：代表的是從nums[0..j]的最長連續遞增子序列。（也可以將其表示為以i為結尾的最長的連續遞增子序列，然后求解得到最大值）
2. 遞推公式：if(nums[i]>nums[i-1]){//滿足遞增才能添加
   ? ? ? ? ? ? ? ? tail[i] = tail[i-1]+1;
   ? ? ? ? ? ? }//if(result>tail[i])tail[i] = result;//比較找到最大值
3. 初始化：默認情況下每個的都是1，因為自身可以當做唯一的那一個遞增子序列。
4. 遍歷順序：由遞推公式可以知道，應該是滿足從小到大的方式進行遍歷。

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {int n = nums.size();//vector<int> dp(n,1);vector<int> tail(n,1);int result = 1;int i = 0;for(int i = 1;i<n;i++){if(nums[i]>nums[i-1]){tail[i] = tail[i-1]+1;}}auto maxs =  max_element(tail.begin(),tail.end());return *maxs;/*for(int j = 1;j<n;j++){i = j;for(;i>0;i--){if(nums[i]<=nums[i-1]){break;}}dp[j] = max(dp[j-1],(j-i+1));//長度}return dp[n-1];*/}
};

3.718最長重復子數組

1.問題描述

找到其中最長重復子數組的長度。

2.問題轉換

按照順序遍歷，如果相同了就長度+1

3.解題思路

1. 每一個位置的nums[i]都有兩種狀態：是否相等
2. 對于相等狀態：即nums1[i-1] == nums2[j-1],此時長度+1，然后比較最大值，更新res
3. 對于不相等狀態：比較最大值更新res
4. 將最大值存放在res中

4.為什么使用動態規劃？

因為每一個位置的值都可以由前面的狀態或者當前的狀態確定。

5.動態規劃的具體實現

1. dp[i][j]數組的含義：代表的是從nums1[0..i-1],nums2[0..j-1]的重復子數組長度。（
2. 遞推公式：?if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}
3. 初始化：默認情況下每個的都是1，因為自身可以當做唯一的那一個遞增子序列。
4. 遍歷順序：由遞推公式可以知道，應該是滿足從小到大的方式進行遍歷。
5. 最終結果存放在res中，因為res的含義是最長的重復子數組的長度。

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