最长上升子序列
`
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N = 1003;
int n;
int a[N];
int f[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for(int i = 1; i <= n; i ++ ) f[i] = 1;
for(int i = 2; i <= n; i ++ )
for(int j = 1; j < i; j ++ )
if(a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
int res = 0;
for(int i = 1; i <= n; i ++ ) res = max(res, f[i]);
cout << res;
return 0;
}`
最长公共子序列
`#include<bits/stdc++.h>
using namespace std;
const int N = 1003;
char a[N], b[N];
int n, m;
int f[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> a + 1 >> b + 1;
f[0][0] = 0;
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= m; j ++ )
{
if(a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
cout << f[n][m] << "\n";
return 0;
}`
最长上升公共子序列
'#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3003;
int n;
int a[N], b[N];
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) cin >> b[i];
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= n; j ++ )
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j]){
for(int k = 0; k < j; k ++ ){
if(b[j] > b[k]){
f[i][j] = max(f[i][j], f[i - 1][k] + 1);
}
}
}
}
}
int res = 0;
for(int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
cout << res << "\n";
return 0;
}'
优化
`
for(int j = 1; j <= n; j ++ )
{
f[i][j] = f[i - 1][j];// a[i] != b[j];
// 以下代码中, i的值始终固定
// 且判断条件始终为a[i] == b[j]
// a[i]不变,则b[j]不变, b[j] > b[k]即 a[i] > b[k];
//所以我们维护一个k从 1 ~ j - 1 的f[i][k]的最大值mx
if(a[i] == b[j]){
//以下循环可以等价为 f[i][j] = max(f[i][j], f[i][1 ~ j - 1] + 1);
//而 max(f[i][j], f[i][1 ~ j - 1] + 1);中 f[i][1 ~ j - 2]在上一轮中以及存在
//所以对于每一轮j 如果 b[j] > b[k] 即 a[i] > b[j] 我们更新最大值mx即可
for(int k = 0; k < j; k ++ ){
if(b[j] > b[k]){
f[i][j] = max(f[i][j], f[i - 1][k] + 1);
}
}
}
}`
优化代码
'#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3003;
int n;
int a[N], b[N];
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) cin >> b[i];
for(int i = 1; i <= n; i ++ )
{
int mx = 1;//每一个b[j]结尾的数,最小的上升子序列为1;
for(int j = 1; j <= n; j ++ )
{
f[i][j] = f[i - 1][j];//a[i] != b[j];
// if(a[i] == b[j]){
// for(int k = 0; k < j; k ++ ){
// if(b[j] > b[k]){
// f[i][j] = max(f[i][j], f[i - 1][k] + 1);
// }
// }
// }
if(a[i] == b[j]) f[i][j] = max(f[i][j], mx);
if(a[i] > b[j]) mx = max(mx, f[i - 1][j] + 1);
}
}
int res = 0;
for(int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
cout << res << "\n";
return 0;
}'
>