最长上升子序列
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N],dp[N];
int main () {
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= n;i++) {
dp[i] = 1;
for (int j = 1;j < i;j++) {
if (a[j] < a[i]) dp[i] = max (dp[i],dp[j]+1);
}
}
int ans = 0;
for (int i = 1;i <= n;i++) ans = max (ans,dp[i]);
cout << ans << endl;
return 0;
}
$时间复杂度(O(n^2))$
$空间复杂度(O(n))$
方法2,二分优化:
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,len = 1;
int a[N],dp[N];
int main () {
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
dp[1] = a[1];
for (int i = 2;i <= n;i++) {
if (a[i] > dp[len]) dp[++len] = a[i];
else {
int t = lower_bound (dp+1,dp+1+len,a[i])-dp;
dp[t] = a[i];
}
}
cout << len << endl;
return 0;
}
$时间复杂度(O(nlog_n))$
$空间复杂度(O(n))$
最长公共子序列
最长公共子序列
方法1,朴素:
#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
string a,b;
int dp[N][N];
int main () {
cin >> n >> m >> a >> b;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
if (a[i-1] == b[j-1]) 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][m] << endl;
return 0;
}
$时间复杂度(O(mn))$
$空间复杂度(O(mn))$