线性dp的两个经典题目：
最长上升子序列（LIS）and 最长公共子序列（LCS）
1.LIS
核心代码
#include <bits/stdc++.h>
using namespace std;
const int maxn =2024;
int cnt=0,ans=1;
int f[maxn],a[maxn],c[maxn];
void out(int x)
{
if(x==0) return ;
out(c[x]);
cout << a[x] <<' ';
}
int main()
{
int x=0,y=0;
while(scanf("%d",&x)!=EOF) a[++cnt] = x;
for(int i=1;i<=cnt;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
{
if(a[i]>a[j] && f[i]<f[j]+1)
{
f[i]=f[j]+1;
c[i]=j;
}
if(ans<f[i])
{
ans=f[i];
y=i;
}
}
}
cout << ans <<endl;
out(y);
return 0;
}
2.LCS
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2024;
int f[maxn][maxn];
char a[maxn],b[maxn];
int main()
{
int ans=0;
cin >> a >> b;
for(int i=1;i<=strlen(a);i++)
{
for(int j=1;j<=strlen(b);j++)
{
if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=0;
ans=max(ans,f[i][j]);
}
}
cout << ans;
return 0;
}