文章目录

问题引入解决方法LIS方法1方法2方法3 LCS方法1方法2

问题引入

最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。

LCS是Longest Common Subsequence的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。 比如，对于char x[]=“aabcd”;有顺序且相互相邻的aabc是其子序列，有顺序但是不相邻的abc也是其公共子序列。即，只要得出序列中各个元素属于所给出的数列，就是子序列。 再加上char y[]=“12abcabcd”;对比出才可以得出最长公共子序列abcd。

解决方法

LIS

设有一串为S：

方法1

很简单，设f[i]为以S中第i个元素为结尾的最长上升子序列（LIS）的长度，然后发现S的LIS长度和S的前缀的LIS长度有关，S的前缀的LIS长度又和S的前缀的前缀的LIS长度有关，就是说这个问题满足最优子结构性质，可以用动态规划的方法来解决： $f[i]=max(f[i],f[i-k]+1),1<=i<=len(S),1<=k<=i$ 复杂度为O（$n^2$）

for(int i=1;i<=len;++i){ for(int k=1;k<=i;++k){ f[i]=max(f[i],f[i-k]+1); } }

方法2

安利一个巨佬的blog

这时我们需要有一个f数组 其作用就是来辅助维护LIS的长度（可以理解为一个擂台，至于原因后面会提到） 同时，我们用一个cnt来记录f数组中的数的个数，cnt初始为0 假设f数组中已经有cnt个数了，现在S中的第i个数正在考虑是否要加入f数组，接下来可以分类讨论：

1.当S[i]>f[cnt]的时候，当然加入f数组2.当S[i]=f[cnt]的时候，当然不能加入3.当S[i]<f[cnt]的时候，这时就找到f中第一个大于S[i]的元素，插入进去，其他小于S[i]的元素不动，因为这样更新后这个f数组更有变长的潜力 loop(i,1,n){ if(i<=1||f[cnt]<b[i]){ f[cnt+1]=b[i]; ++cnt; } else f[lower_bound(f+1,f+cnt+1,b[i])-f]=b[i]; }

可能看到这里有个疑问：为什么S[i]<f[cnt]时会这样操作呢？ 首先明确一点，第3个操作不会改变f数组中数字的单调性，这样的话lower_bound是可以正确执行的 那么上面的第二个else就是处理情况3的，这时将S[i]插入，虽然使得f数组内的数不再满足在原串内的相对位置关系（可能S中i在j前面，但由于j很小，f中j在i前面），但是这时候的cnt并没有改变，也就是说，插入S[i]并没有立即更新cnt（LIS长度），而是保留了生成一个更长的LIS的可能性。若真的能够生成一个新的LIS，那么这个LIS在cnt位置的数f[cnt]一定小于原来的f[cnt]，这个时候就cnt才会被更新，也就是找到了一个更长的LIS（实在不行可以模拟一下，肯定秒懂）

这种方法的复杂度为$O(nlogn)$

方法3

考虑到方法一中有一步为找i前面最大的f值，这一步使得算法时间复杂度飙升到了n方，所以我们可以优化这一步：用线段树（树状数组）来优化 设f[i]为以值i为结尾的最大的LIS的长度，则对于一个新数x: $f[x]=getpremax(x)+1$ (getpremax（i）就是在f数组中找小于等于i的数的最大的f值) 这个getpremax操作显然可以用线段树来操作（当然，其他数据结构也可以，只是常数不同罢了） 具体操作的思路就是不断的查询比自己小的数对应的f的最大值，以此来更新自己的f值然后插入线段树内（可以用排队形象理解）：

先把数据离散一下（不知道我这么做有没有问题）： 原数据：1 4 6 9 10 34 532 离散后：1 2 3 4 5 6 7枚举i，对于每一个i，data[i]为数列中第i个数的值，则 $f[data[i]]=query(1,data[i]-1,1,n,1)+1$ $(query（l,r,nl,nr,rt）就是线段树中查询区间[l,r]的最大值)$ 更新完$f[data[i]]$后，就将新的值插入进线段树中： $update(data[i],1,n,1,f[data[i]])$ $（update（pos,l,r,rt,w）即将pos位置的值修改成f[data[i]]）$最后遍历f数组，找到最大值即为答案 int n,first; int data[maxn]; int f[maxn]; int map[maxn]; inline void lisan(){//假设题目中最大的数不超过n int cnt=0;clean(map,0); loop(i,1,n) if(!map[data[i]]) map[data[i]]=true; loop(i,1,n){ if(map[i]&&cnt==0) map[i]=++cnt,first=i; else if(map[i]&&cnt)map[i]=++cnt; } } int maxx[maxn<<2]; void update(int pos,int nl,int nr,int rt,int w){ if(nl==nr&&nr==pos){ maxx[rt]=w;return; }int mid=(nl+nr)>>1; if(mid>=pos)update(pos,nl,mid,rt<<1,w); else if(mid<pos)update(pos,mid+1,nr,rt<<1|1,w); maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]); } int query(int l,int r,int nl,int nr,int rt){ if(l<=nl&&nr<=r) return maxx[rt]; int mid=(nl+nr)>>1; int res=0,ans=0; if(mid>=l)res=query(l,r,nl,mid,rt<<1); ans=max(ans,res); if(mid<r)res=query(l,r,mid+1,nr,rt<<1|1); ans=max(ans,res); return ans; } int main(){ loop(i,1,n){ if(i==1) update(map[data[i]],1,n,1,1),f[map[data[i]]]=1; else{ int res=0; if(data[i]!=first) res=query(1,map[data[i]]-1,1,n,1); else res=0; update(map[data[i]],1,n,1,res+1); f[i]=res+1; } } int res=0; loop(i,1,n) res=max(res,f[i]); return 0; }

LCS

设有两个串A，B；

方法1

这个问题，通过仔细的分析也不难发现它可以用DP来解决： 设f[i][j]表示以第一个串A第i个字符为结尾，第二个串B第j个字符为结尾的两个子串的LCS的长度，则有

1.$若A[i]==B[j]:f[i][j]=max(f[i-1][j-1]+1,f[i][j])$2.$若A[i]!=B[j]:f[i][j]=max(f[i-1][j],f[i][j-1])$$特别的，若i=0或j=0，f[i][j]=0$

复杂度为$O(lenA\ast lenB)$

memset(f,0,sizeof(f)); for（int i=1;i<=lenA;++i){ for(int j=1;j<=lenB;++j){ if(A[i]==B[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); else if(A[i]!=B[j]) f[i][j]=max(f[i-1][j],f[i][j-1]); } }

方法2

这个方法并不适用于所有的LCS问题 当且仅当A和B中的元素都相同（或B（A）中有A（B）的所有元素，B(A)中有A(B)没有的元素）时适用 这个时候可以将A和B中的元素按照某种规则离散一下然后求一个LIS就可以了： 假设lenA>=lenB 那么就将A[i]映射到i,这样的话就将A[1]到A[lenA]映射到了1到lenA这lenA个数 再将B按照同样的规则变化，假设之后得到的数组为C，那么我们只需要对C求一个LIS就可以啦！（相信其中的道理很简单吧！） 这种方法的复杂度取决于你求LIS的复杂度