LIS(最长上升子序列)
求长度
dp - O(n2)
动态规划的做法
令f[i]表示以第i个元素结尾的LIS长度
则有: f[i]=max(f[i],f[j]+1),(a[j]<a[i],j<i)
通过枚举f[i]与f[j]来不断转移状态，然后不断枚举更新最大值
Sample Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<cstdio>
using namespace std;
#define maxn 10005
int f[maxn],a[maxn];
int main()
{
int n,Max = 0;
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
for(int i = 1;i <= n;i ++)
{
f[i] = 1;
for(int j = 1;j < i;j ++)
if(a[j] < a[i] && f[i] < f[j] + 1) f[i] = f[j] + 1;
}
for(int i = 1;i <= n;i ++) if(f[i] > Max) Max = f[i];
printf("%d",Max);
return 0;
}
|
该算法可以求出具体的最长上升子序列，但是在只要求最长上升子序列长度时，我们通常可以考虑更优的O(n log2 n)的做法
dp+树状数组O(n log2 n)
注意到我们在状态转移的时候要枚举f[j]的最大值来转移，我们可以考虑使用数据结构来维护从而优化一下，只要是支持单点修改和区间最值查询的数据结构都可以这么做，分块(O(nn))和树状数组(O(n log2 n))，线段树(O(n log2 n))之类的都行，但是因为树状数组比较好写，所以我们只讲解树状数组的写法
- 先按权值排序，排序之后再查询序号前最大的f[j]来转移，但是有一点要注意，我们求的是LIS，是严格上升的，所以我们遇到重复的权值的时候应该要放在最后一次性处理，不然后面的重复了的f[]就能够用前面相同的元素来转移，导致最后的答案是错误的
Sample Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 1000007
int n,Dp[maxn],Ans,Max[maxn];
struct Node{int w,i;}A[maxn];
#define lowbit(x) ((x) & (-x))
inline bool cmp(Node A , Node B){return A.w < B.w;}
inline void Update(int Pos , int w)
{
for(int i = Pos;i <= n; i += lowbit(i))
Max[i] = max(Max[i] , w);
}
inline int Query(int Pos)
{
int Ret = 0;
for(int i = Pos ; i ; i -= lowbit(i))
Ret = max(Ret , Max[i]);
return Ret;
}
int main()
{
scanf("%d" , &n);
for(int i = 1;i <= n;i ++) scanf("%d" , &A[i].w) , A[i].i = i;
sort(A + 1 , A + 1 + n ,cmp);
int Last = 1;
for(int i = 1;i <= n;i ++)
{
if(A[i].w != A[i - 1].w && i - 1)
{
for(int j = Last;j <= i - 1;j ++) Update(A[j].i , Dp[j]);
Last = i;
}
Dp[i] = Query(A[i].i) + 1;
Ans = max(Ans , Dp[i]);
}
printf("%d" , Ans);
return 0;
}
|
- 维护f[]这个数组，但是用权值作为数组下标，然后不需要sort，顺序枚举就可以了，关于值的大小我们可以直接查找(树状数组)，注意到范围很大时，我们可以进行离散化
Sample Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 1000007
int n,ans,f[maxn];
struct Node{int val,num;}z[maxn];
#define lowbit(x) ((x) & (-x))
inline void modify(int x,int y)
{
for(;x < maxn ;x += lowbit(x))
f[x] = max(f[x],y);
return ;
}
inline int query(int x)
{
int res = 0;
for(;x;x -= lowbit(x)) res = max(res,f[x]);
return res;
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&z[i].val);
for(int i = 1;i <= n;i ++)
{
int Max = query(z[i].val - 1);
modify(z[i].val , ++ Max);
ans = max(ans,Max);
}
printf("%d",ans);
return 0;
}
|
贪心+二分O(n log2 n)
贪心的做法
维护一个单调栈，然后根据栈定元素元素和当前元素作比较来选择最优策略，定义stack[]为单调栈，栈顶元素为stack[top]，当前序列的第i个元素为a[i]
- 如果stack[top]<a[i] 那么满足单调，可以直接压入栈中
- 如果stack[top]⩾a[i] 那么这个时候插入就不满足单调了，那么我们考虑在单调栈中进行二分查找，然后找到第一个stack[j]⩾a[i]进行替换即可
Q:为什么进行替换这一贪心的策略是可行的?
A: 因为这样做并没有增长栈的长度，而且这么一接下去就可以有更好的方案，其实感性的理解就是一个在栈中不止一个序列，可以理解为两条或者更多，但是在替换之后的元素的压入可以应用到每一条序列中作出贡献，比如下面的这个例子
Input:
稍稍根据上面的贪心决策不难推出这样的一个过程:
- stack[1] = {1};
- stack[2] = {1,4};
- stack[2] = {1,2};
- stack[3] = {1,2,5};
- stack[3] = {1,2,3};
看到第3步中的替换过程，4变成了2，其实4也存在{1,4,5}这样的最长上升子序列，但是如果后面还有数字就没有2更优，在我们替换过后，4其实也在参与，但是因为我们发现的更加优越的2，所以4的贡献肯定比2的贡献要小，可以直接替换掉
Warning
该O(n log2 n)算法其实不能求出具体的最长上升子序列，因为中间在替换的过程中就已经把原有的顺序给打乱了，对于替换掉的元素，不知道是否能够对于后面的最长上升子序列作出价值，所以是不可以的
Sample Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100005
int a[maxn],d[maxn];
int main()
{
int n,len = 1;
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
d[1] = a[1];
for(int i = 2; i <= n; i ++)
{
if(d[len] < a[i]) d[++ len] = a[i];
else *lower_bound(d + 1 , d + 1 + len , a[i]) = a[i];
}
printf("%d",len);
return 0;
}
|
求具体LIS序列
此题dp−O(n2)中的思想可以应用，相应的，我们可以再加上一个树状数组来优化算法的时间复杂度到O(n log2 n)，通过记录一个结尾对应的序列中的前驱来优化算法的空间复杂度至O(n)，然后就十分的可做了，因为树状数组有两种写法，作者在此只写出一种做法的解法，另外一种解法可以让读者自行思考，不过最好是离散化一下
Sample Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 1000007
int n,Dp[maxn],Ans,Max[maxn],Max_num[maxn],pre[maxn],num = 0,a[maxn];
struct Node{int w,i;}A[maxn];
#define lowbit(x) ((x) & (-x))
inline bool cmp(Node A , Node B){return A.w < B.w;}
inline void Update(int Pos , int w,int Num)
{
for(int i = Pos;i <= n; i += lowbit(i))
if(Max[i] < w) Max[i] = w,Max_num[i] = Pos;
return ;
}
inline int Query(int Pos)
{
int Ret = 0;num = 0;
for(int i = Pos ; i ; i -= lowbit(i))
if(Ret < Max[i]) Ret = Max[i],num = Max_num[i];
return Ret;
}
inline void Output(int first)
{
if(!first) return ;
else Output(pre[first]);
printf("%d ",a[first]);
return ;
}
int main()
{
scanf("%d" , &n);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]),A[i].w = a[i],A[i].i = i;
sort(A + 1 , A + 1 + n ,cmp);
int Last = 1,first = 0;
for(int i = 1;i <= n;i ++)
{
if(A[i].w != A[i - 1].w && i - 1)
{
for(int j = Last;j <= i - 1;j ++) Update(A[j].i , Dp[j],j);
Last = i;
}
Dp[i] = Query(A[i].i) + 1;
pre[A[i].i] = num;
if(Ans < Dp[i]) Ans = Dp[i],first = A[i].i;
}
printf("%d\n" , Ans);
Output(first);
return 0;
}
|
LCS(最长公共子序列)
求长度
O(nm)
动态规划做法，其实原理很简单，就是看当前的位上是否匹配的问题，然后根据这个来转移状态
设有长度为n的串S与长度为m的串T，用f[i,j]表示S串前i个字符与T串前j个字符的LCS则有:
f[i,j]=max(f[i−1,j],f[i,j−1],(f[i−1,j−1]+1)∗[Si=Tj])
也就是说，无论如何，一定有
f[i,j]=max(f[i−1,j],f[i,j−1])
讨论特殊情况:当Si=Tj时
f[i,j]=max(f[i,j],f[i−1,j−1]+1)
所以我们可以从这推出结果，然后f[n,m]就是最后的答案
因为f[i]总是会从f[i−1]这一维度转移过来，所以我们可以考虑用滚动数组来优化空间复杂度
Sample Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 5e3 + 7;
int n,m,tmp;
char a[maxn],b[maxn];
int f[2][maxn];
int main()
{
scanf("%s",a + 1);
n = strlen(a + 1);
scanf("%s",b + 1);
m = strlen(b + 1);
int now = 0;
for(int i = 0;i <= n;i ++)
{
now ^= 1;
for(int j = 1;j <= m;j ++)
{
f[now][j] = max(f[now ^ 1][j],f[now][j - 1]);
tmp = f[now ^ 1][j - 1] + 1;
if(a[i] == b[j] && f[now][j] < tmp) f[now][j] = tmp;
}
}
printf("%d",f[now][m]);
return 0;
}
|
O(n log2 n)
其实我先讲LIS是有原因的，我们可以尝试着去探求这两个问题之间的联系
如果我可以通过把这个原来的序列转化为另外一个序列然后求LIS来得到LCS就好了，那么怎么去转换这两个问题呢?
我们不难发现，LIS是用来求最长上升子序列的，所以当一个序列是升序排序，另外一个序列乱序时，求两个序列的LCS其实就是在求乱序序列的LIS，因为有一个序列是升序的，所以一定存在乱序序列的最长上升子序列与升序序列的序列有最长公共子序列，所以就可以求出来了
所以我们在一开始输入A序列的时候就将它序列中的元素逐一编号，然后再在B序列给对应的元素编上在A序列中的编号，也就是B序列中元素在A序列中的位置
比如说
编号之后就是
然后去求改变后的B序列的LIS就好了，也就是答案2 4 5，长度为3
Warning
-
在两个序列有不同元素的时候，处理的时候要去掉不同的元素，否则LIS可能会包含另外一个序列没有的元素而导致答案错误
-
在两个序列中有重复的元素时，不能用该方法处理
比如说:
我们可以发现这两个序列的LCS是ab或ba长度为2
但是在处理赋值的过程中有点小麻烦
我们发现在处理完的序列中有重复的数字，这是因为在第一次给A中的元素赋值的时候，我们对于重复的元素赋了两次值，于是就导致了序列中数字所对应的位置有多个，在处理过程中会覆盖掉
那你可能会说:我不覆盖掉不就是了
然后你这个naive的想法可能就会泡汤，因为在某些情况下，不管你怎么赋值，其实都不一定会是一个升序的序列，这个时候求另外一个序列的LIS就没有意义了，因为你本身的序列就不是升序，我求一遍升序就与另一个序列无关了
- 该算法不能求出具体的LCS序列，所以如果题目要求出具体的子序列时不能使用该算法，原因同LIS的n log2 n做法
Sample Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100005
int a[maxn],b[maxn];
int d[maxn],stack[maxn],len = 0;
int main()
{
int n;
scanf("%d",&n);
for(int i = 0;i < n;i ++)
{
scanf("%d",&a[i]);
d[a[i]] = i + 1;
}
for(int i = 0;i < n;i ++)
{
scanf("%d",&b[i]);
b[i] = d[b[i]];
}
stack[1] = b[0],len = 1;
for(int i = 0;i < n;i ++)
{
if(stack[len] < b[i]) stack[++ len] = b[i];
else *upper_bound(stack + 1,stack + 1 + len,b[i]) = b[i];
}
printf("%d",len);
return 0;
}
|
求具体LCS序列
我们可以考虑借鉴一下LIS的写法，记录前驱和最大值开头的数值，然后进行递归倒序输出，但是这个时候我们的dp[]不能用数据结构来优化，所以我们的算法是O(nm)的，具体代码请读者自行思考
LCIS(最长公共上升子序列)
我们可以结合上面的LIS和LCS的思想来思考这个问题
LIS:
令f[i]表示以第i个元素结尾的LIS长度
则有: f[i]=max(f[i],f[j]+1),(a[j]<a[i],j<i)
LCS:
设有长度为n的串S与长度为m的串T，用f[i,j]表示S串前i个字符与T串前j个字符的LCS则有:
f[i,j]=max(f[i−1,j],f[i,j−1],(f[i−1,j−1]+1)∗[Si=Tj])
稍加组合思考我们可以发现:
当f[i,j]表示A序列前i个元素和B序列前j个元素的LCIS，t表示LCIS的结尾元素位置，则有:
f[i,j]=f[i−1,j],Ai=Bj
f[i,j]=max(f[i−1,j],f[i−1,t]+1),Ai=Bj
又发现f[i]这一维每次都是从f[i−1]这一维转移过来，所以我们可以用滚动数组优化一下得到:
fi代表序列A前i个元素与序列B的LCIS，t为结尾位置，有
fj=ft+1,Ai=Bj
在计算LCIS的长度的过程中我们可以顺便记录前驱然后输出具体的序列，所以就可以用O(nm)的时间复杂度算出LCIS长度与LCIS的具体序列
Sample Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<cstdio>
using namespace std;
#define maxn 505
int a[maxn],b[maxn],f[maxn],pos[maxn];
void output(int x)
{
if(!x) return;
output(pos[x]);
printf("%d ",b[x]);
}
int main()
{
int n,m,Max = 0;
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i = 1;i <= m;i ++) scanf("%d",&b[i]);
for(int i = 1,t = 0;i <= n;i ++,t = 0)
for(int j = 1;j <= m;j ++)
{
if(a[i] == b[j]) f[j] = f[t] + 1,pos[j] = t;
if(a[i] > b[j] && f[t] < f[j]) t = j;
}
for(int i = 1;i <= m;i ++)
if(f[i] > f[Max]) Max = i;
printf("%d\n",f[Max]);
output(Max);
return 0;
}
|
至此，我们已经讨论了LIS，LCS与LCIS三种基础的动态规划类型，算法与算法之间的联系可见一斑了
致谢
- 感谢洛谷上的部分优质题解，我从题解中找到了很多的思路，受教良多
- LiangShineSky 大佬的指点