1.最长上升子序列（LIS）
子序列： 1.可以不连续 2.相对位置不变
dp[i][j] 表示前i位置，最大值为j的LIS长度 1. dp[i-1][j] 前i-1位置，最大值为j的LIS长度 (没有考虑a[i]) 2. dp[i][j]=dp[i-1][k]+1 (j==a[i] k < j) ans=max(dp[n][i]) DP复杂度：状态数量*单个状态转移复杂度 O(n^2) 空间 O(n^2)序列： 前i个位置，以第i个位置结尾。
f[i] 以第i个位置结尾的LIS长度 f[i] <- f[j]+1 (j< i a[j]< a[i]) ans=max(f[i]) O(n^2) 空间 O(n)for(int i=1;i<=n;i++){ f[i]=1; for(int j=1;j O(nlogn):
1. 用一个数组(栈)来维护最可能成为LIS的序列 （和DP没有关系） 2. 用树状数组来优化第二种DP（有推广意义）。1 3 5 6 4 7 8
[1,3,5,6] 4 [1,3,4(5),6] 5 [1,3,4(5),5(6),6] 向前查找位置（二分或STL）nlogn upper_bound: “元素值>查找值”的第一个元素的位置 lower_bound: “元素值>=查找值”的第一个元素的位置#include#include #include using namespace std;int a[40005];int d[40005];int main(){ int n; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); if (n==0) { printf("0\n"); return 0; } d[1]=a[1]; int len=1; for (int i=2;i<=n;i++) { if (a[i]>d[len]) d[++len]=a[i]; else { int j=lower_bound(d+1,d+len+1,a[i])-d; //找到第一个>=它的d的下标 d[j]=a[i]; } } printf("%d\n",len); return 0;}
树状数组： 1. 求前缀和， 2.单点加减
int ask(int pos){ int ret=0; while(pos>0){ ret+=c[pos]; pos-=lowbit(pos); } return ret;}void add(int pos,int w){ while(pos<=n){ c[pos]+=w; pos+=lowbit(pos); }} 树状数组 1. 求前缀最大值， 2.单点修改(往大里改)
int ask(int pos){ int ret=0; while(pos>0){ ret=max(ret,c[pos]); pos-=lowbit(pos); } return ret;}void modify(int pos,int w){ while(pos<=n){ c[pos]=max(c[pos],w); pos+=lowbit(pos); }} for(int i=1;i<=n;i++){ f[i]=1+max(0,b[0],b[1],b[2],...,b[a[i]-1]); b[a[i]]=f[i];} for(int i=1;i<=n;i++){ f[i]=ask(a[i]-1)+1; modify(a[i],f[i]);} 2.最长公共子序列
a 1 4 5 2 3
b 1 5 2 4 31 5 2 3
1) 前…个元素
f[i][j] a串前i个元素，b串前j个元素的LCS长度 a[i] != b[j] f[i][j] <- f[i-1][j] f[i][j-1] a[i] == b[j] f[i][j] <- f[i-1][j-1]+1O(1)*O(n^2)
f[n][m]
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){ if(a[i] != b[j]) f[i][j]=max( f[i-1][j] , f[i][j-1]); else f[i][j]=f[i-1][j-1]+1; } }2) 以…结尾
f[i][j] a串以i结尾，b串以j结尾的LCS长度
a[i] != b[j] f[i][j] = 0
a[i] == b[j] f[i][j] <- f[k][l] (k< i l< j)O(n^2)*O(n^2)
ans=max(f[i][j])
3.LICS(LCIS):
1) 前…个元素
f[i][j] a串前i个元素，b串前j个元素的LICS长度 无法转移f[i][j][k] a串前i个元素，b串前j个元素的LICS长度最大值为k
a[i] != b[j] f[i][j][k] <- f[i-1][j][k] f[i][j-1][k] a[i] == b[j] && a[i]==k f[i][j][k] <- f[i-1][j-1][l] l< kO(n^3) 空间 (空间可以滚动数组优化) n^3 时间
ans=max(f[n][m][i]) 2) 以…结尾 f[i][j] a串以i结尾，b串以j结尾的LICS长度a[i] != b[j] f[i][j] = 0
a[i] == b[j] f[i][j] < - f[k][l]+1 (k < i l< j a[k]==b[l] a[k]< a[i] )O(n^2)*O(n^2)
O(n^2)空间 O(n^4)时间
ans=max(f[i][j])
3)
f[i][j] a串前i个元素，b串以j结尾的LICS长度a[i] != b[j] f[i][j] <- f[i-1][j]
a[i] == b[j] f[i][j] <- f[i-1][k] +1 (k< j b[k]< b[j])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]; else{ f[i][j]=1; for(int k=1;k< j;k++){ if(b[k]< b[j]) f[i][j]=max(f[i][j],f[i-1][k]+1); } } }} O(n^2)空间 O(n^3)时间
ans=max(f[n][i])
O(n^2logn)
int mx[];for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ // LIS 树状数组优化 mx[j] = ask(b[j]-1); modify(b[j],f[i-1][j]); } for(int j=1;j<=m;j++){ // LCS if(a[i]!=b[j]) f[i][j]=f[i-1][j]; else{ f[i][j]=mx[j]+1; } }} O(n^2)? 思考
//By Menteur_Hxy#include#include using namespace std;const int MAX=3010;int n,m,top;int a[MAX],b[MAX],f[MAX][MAX];int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]);// scanf("%d",&m); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++){ int maxn=0; for(int j=1;j<=n;j++) { if(a[i]!=b[j]) f[i][j]=f[i-1][j]; else f[i][j]=maxn+1; if(a[i]>b[j]) maxn=max(maxn,f[i-1][j]); } } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,f[n][i]); printf("%d",ans); return 0; }
输出方案
f[i] <- max( f[j]+1) j< i g[i] jf[n] g[n] f[g[n]] g[f[g[n]]]
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
int g[][]// 记录转移
if(f[i+1][j]>f[i+1][j+1]){ f[i][j]=f[i+1][j]+a[i][j]; g[i][j]=j;}else{ f[i][j]=f[i+1][j+1]+a[i][j]; g[i][j]=j+1;}