1.LIS :
给定一个序列，求它的最长上升子序列(n<=2000)
第一种 O（n^2）：
dp[i] 为以i为开头的最长上升子序列长度
code1:
#include<cstdio>
#include<iostream>
using namespace std;
int n,ans;
int a[2005],dp[2005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
dp[i]=1;
}
for(int i=1;i<=n;i++) {
for(int j=1;j<i;j++)
if(a[j]<a[i]) dp[i]=max(dp[j]+1,dp[i]);
if(ans<dp[i]) ans=dp[i];
}
printf("%d",ans);
return 0;
}第二种 O(nlogn)：
最长上升子序列存在O(N log N)时间复杂度的算法，概述如下：
考虑两个数a[x]和a[y]，若x < y且g[x]==g[y]，那么在转移的过程中，选择a[x]更有潜力（证明是显而易见的，可以自己设计几组数据加深理解），可以获得最优的值，所以当g数组的值一样时，应选择最小的数。
按照g[i]==k分类，记录g[i]==k的所有i的最小值，g有两个特点：
1)f[i]在计算过程中单调不升
2)f数组是有序的，g[i]<=g[i+1]
根据这些性质，可以方便地求解：
1)设当前求出的LIS长度为ans（初始值为1），当前元素为a[x]
2)如果a[x]>g[ans]，直接加入f数组的末尾，且ans++；否则在f数组中二分查找，找到第一个比a[x]小的数字g[k]（使用二分查找实现），g[k+1]=a[x]，这样做保证a[x] < =g[k+1]（根据性质1，2）
3)最后的ans即为答案
代码中dp[i] 表示长度为i的上升子序列末尾元素最小是多少
code2:
#include<cstdio>
int n,ans;
int a[2005],dp[2005];
int find(int l,int r,int x){//二分查找 用循环也行这里递归
int mid=(l+r)/2;
if(l==mid) return l<x?r:l;//如果前一个满足选前一个不然选第二个
if(dp[mid]<x) return find(mid,r,x);
else return find(l,mid,x);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dp[++top]=a[1];
for(int i=2;i<=n;i++) {//若a[i]==dp[ans] 跳过
if(a[i]>dp[ans]) dp[++ans]=a[i];//如果恰好可以接上
else if(a[i]<dp[ans]) dp[find(1,ans,a[i])]=a[i];//找到第一个不小于的换掉（手动跑下就明白了）
}
printf("%d",ans);
return 0;
}2.LCS
给定两个长度分别为n,m的序列S,T求他们的最长公共子序列
设 dp[x][y] 表示S[1..x]与T[1..y]的最长公共子序列的长度
分三种情况:
1.S[x]不在公共子序列中：该情况下dp[x][y]=dp[x-1][y];
2.T[x]不在公共子序列中：该情况下dp[x][y]=dp[x][y-1];
3.当S[x]=T[y]时，S[x]和T[y] 均在公共子序列中：该情况下dp[x][y]=dp[x-1][y-1]+1;
最终dp[x][y] 取以上情况的最大值。
边界 若x=0或y=0 dp[x][y] =0。
复杂度：O（n^2）
code：
#include<cstdio>
int n,m;
int s[2][5000],dp[5000][5000];
int max(int x,int y,int z){
x=x>y?x:y;
x=x>z?x:z;
return x;
}
int main(){
scanf("%d",&n);
for(int i=0;i<=1;i++)
for(int j=1;j<=n;j++)
scanf("%d",&s[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) {
if(s[0][i]==s[1][j]) dp[i][j]=dp[i-1][j-1]+1;
dp[i][j]=max(dp[i][j],dp[i-1][j],dp[i][j-1]);
}
printf("%d",dp[n][n]);
return 0;
}