最長上升子序列

定義：給出一個數字序列（arr），求出其中長度最長的數值嚴格遞增的子序列

做法一：使用動態規劃，我們定義dp[i]為以arr[i]結尾的最長上升子序列的長度。

#include<bits/stdc++.h>
using namespace std;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;vector<int> v(n+1,0);for(int i=1; i<=n; i++) cin>>v[i];vector<int> dp(n+1);dp[1] = 1;int res=1;for(int i=2; i<=n; i++){int maxn = 0;for(int j=1; j<i; j++){if(v[j]<v[i]) maxn = max(maxn,dp[j]);}dp[i] = maxn+1;res = max(res,dp[i]);	}cout<<res<<endl;return 0;
}

做法二：我們如果僅僅需要求出最后的結果，可以考慮貪心＋二分查找來優化。

我們對于遍歷到的每一個元素，我們都在dp數組中去尋找第一個大于等于它的元素，如果沒有，代表它最大，所以直接加入dp，如果找到，則更新這個位置為當前元素，以此來保證為未來提供更小的末尾序列。

#include<bits/stdc++.h>
using namespace std;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;vector<int> v(n+1,0);for(int i=1; i<=n; i++) cin>>v[i];vector<int> dp;for(int i=1; i<=n; i++){int now = v[i];auto x = lower_bound(dp.begin(),dp.end(),now);if(x==dp.end()) dp.push_back(now);else *x = now;}cout<<dp.size()<<endl;return 0;
}

最長公共子序列

定義：給出兩個數字序列，求出兩個數字序列的最長子序列的長度。

若兩個序列（記為arr1，arr2）中的數字是可以重復的，即最普遍的情況：

直接采用動態規劃做法，我們定義dp[i][j]為arr1的前i個數和arr2的前j個數的最長子序列的長度。

我們對兩個數組均進行從頭遍歷，若arr1[i]==arr2[i]，那么dp[i][j]可以直接由dp[i-1][j-1]加一得出。若不等，則為max（dp[i-1][j],dp[i][j-1]）。

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;vector<int> v1(n+1,0);vector<int> v2(n+1,0);for(int i=1; i<=n; i++) cin>>v1[i];for(int i=1; i<=n; i++) cin>>v2[i];vector<vector<int>> dp(n+1,vector<int>(n+1,0));for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(v1[i]==v2[j]) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}	cout<<dp[n][n]<<endl;return 0;
}

我們發現，當前狀態只與上一個階段的狀態以及當前狀態的j-1有關，所以我們可以去掉第一個維度

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;vector<int> v1(n+1,0);vector<int> v2(n+1,0);for(int i=1; i<=n; i++) cin>>v1[i];for(int i=1; i<=n; i++) cin>>v2[i];vector<int> dp(n+1,0);for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(v1[i]==v2[j]) dp[j] = dp[j-1]+1;else dp[j] = max(dp[j],dp[j-1]);}}cout<<dp[n]<<endl;return 0;
}

這樣做的時間復雜度是O(n2)的

若兩個序列（記為arr1，arr2）是排列，即元素不重復【洛谷：P1439 【模板】最長公共子序列】：

我們可以將問題轉換為LIS來做。

我們將arr1中的元素值和位置做一個映射，然后將arr2中的元素全部轉換為位置。

理由：因為公共子序列要求兩個序列中順序相同，而如果arr1和arr2具有公共子序列，那么他們的索引一定都是遞增的，所以最長遞增子序列此時就是最長公共子序列。

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;vector<int> v1(n+1,0);vector<int> v2(n+1,0);vector<int> pos(n+1,0);vector<int> arr(n+1,0);for(int i=1; i<=n; i++){cin>>v1[i];pos[v1[i]]=i;}for(int i=1; i<=n; i++){cin>>v2[i];arr[i] = pos[v2[i]];	}vector<int> dp;for(int i=1; i<=n; i++){int now = arr[i];auto x = lower_bound(dp.begin(),dp.end(),now);if(x==dp.end()) dp.push_back(now);else *x = now;}cout<<dp.size()<<endl;return 0;
}

這樣的復雜度是O（nlogn）