最长公共子序列

算法

动态规划的中的最长公共子序列示例题。

示例

题目

设计一个O(n^2^)时间的算法,找出由n个数组成的序列的最长单调递增子序列。

简要分析

题目可以看做原序列和排序后序列求最长公共子序列。

基础

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。

设给定序列$X=\{x_1,x_2,x_3,…x_m\}$,若存在子序列$Z=\{z_1,z_2,z_3,….,z_k\}$,那么,

必定存在一个严格递增的下标序列$\{i_1,i_2,i_3,….i_k\}$,使得所有$j$=1,2,3,…,k,都有$z_j=x_{i_j}$

例如:

$X$=$\{A,B,C,B,D,B,A\}$,则其子序列$Z$=$\{B,C,D,A\}$,相应的下标序列为{2,3,5,7}(下标从1开始)

此时,当$j$=1时,$z_1$=$B$,x的下标为$i_1$,即$x_{i_1}$,$i_1$也就是下标序列中的第一位,即2,

所以,$z_1=x_2=B$,同理,当$j$=4时,$z_4=x_{i_4}=x_7=A$

当给定两个序列$X$和$Y$,且$Z$同时为两者的子序列时,则称$Z$为$X$和$Y$的公共子序列

例如:

$X=\{A,B,C,B,D,B,A\},Y=\{B,D,C,A,B,A\}$

若$Z=\{B,C,A\}$,则$Z$是$X,Y$的公共子序列

若$Z=\{B,C,B,A\}$,则$Z$是$X,Y$的公共子序列,同时也是最长公共子序列

计算最长公共子序列

设序列$X=\{x_1,x_2,x_3,…x_m\}$,和序列$Y=\{y_1,y_2,y_3,….,y_n\}$的最长公共子序列为$Z=\{z_1,z_2,z_3,….,z_k\}$,则有三种情况

  1. 若$x_m=y_n$,则$z_k=x_m=y_n$,且$z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的最长公共子序列
  2. 若$x_m \ne y_n$且$z_k \ne x_m$,则$Z$是$X_{m-1}$和$Y_n$的最长公共子序列
  3. 若$x_m \ne y_n$且$z_k \ne y_n$,则$Z$是$X_m$和$Y_{n-1}$的最长公共子序列
①$x_m=y_n$,说明$X$和$Y$的最后一个元素相同,而$Z$是$X$和$Y$的最长公共子序列,而最长自然最好是从头到尾,既然两者的尾元素相同,那自然应该包含在最长公共子序列中,且应是最后一位。三者同时将最后一位去掉,即得到$Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的最长公共子序列

证:

若$z_k \ne x_m$,则因为$Z$是$X$和$Y$的最长公共子序列,且$x_m=y_n$,则说明$\{Z,x_m/y_n\}$也应该是$X$和$Y$的公共子序列,因为$Z$的长度是$k$,而$\{Z,x_m/y_n\}$的长度为$k+1$,$k+1>k$,这与”$Z$是$X$和$Y$的最长公共子序列设定“冲突,所以必有$z_k=x_m=y_n$,即当$x_m=y_n$时,$x_m/y_n$必定在最长子序列$Z$中。

②/③$Z$是$X$和$Y$的最长公共子序列,而$z_k$是$Z$中的最后一位,$x_m$是$X$中的最后一位,若$z_k \ne x_m$,说明$x_m$不包含于$Z$中,即$X_m$不是最长公共子序列的一部分,那么可以将其去掉,即最长公共子序列存在于$X_{m-1}和Y_n$中

分析递归结构

由上可知,当$x_m=y_n$时,找出$x_{m-1}和y_{n-1}$的最长公共子序列,在气候加上$x_m$,即是X和Y的最长公共子序列;当$x_m \ne y_n$时,则分别求$X_{m-1}和Y_n$的最长公共子序列,以及$X_m和Y_{n-1}$的最长公共子序列,并比较得到较长的那个序列,即为$X,Y$的最长公共子序列。

用C[i][j]记录序列$X_i和Y_j$的最长公共子序列的长度。

例:

C[5][7]即是$X_5=\{x_1,x_2,….,x_5\}$和$Y_7=\{y_1,y_2,….,y_7\}$的最长公共子序列

当$i=j=0$时,说明$X$和$Y$都是空序列,那么最长公共子序列的长度也自然是0,得到公式

DP数组C

图表分析

另外设一个数组b[i][j]用来记录符合哪一种情况,即上述方式中的四种情况。

X=[5,2,3,4,8,6,9],Y为升序的X,Y=[2,3,4,5,6,8,9]

C表:

DP数组C

b表:(第一种情况用作边界条件,设上述第二种情况为1,第三种情况的左侧大为2,右侧大为3)

DP数组b

示例:

当$i$=1的时候,$x_1 \ne y_1,i,j \ne 0$那么看第三种方案中的两种情况,$C[i-1][j]=C[0][1]=0$,$C[i][j-1]=C[1][0]=0$,这里将他归入”2“,即$C[i-1][j]\ge C[i][j-1]$,所以此时$C[1][1]=C[i-1][j]=C[0][1]=0$,为”2“情况,所以$b[1][1]=2$,依次类推,直到$j=4$时,$x_1=y_4$,此时满足第二种情况,所以$C[1][4]=C[0][3]+1=1$,$b[1][4]=1$

依次类推,当$i=7,j=7$时,返回$C[7][7]$即为最长子公共序列的长度,并返回$b$数组用于输出该最长子公共序列。

DP数组b

如上图所示,根据b数组进行查找输出。

首先$b[7][7]=1$,说明$x_7$在最长公共子序列中可以输出,但应是最晚输出,因为是1,所以找$C[6][6]$,即左上角,左上角为2,则说明该值由$C[i-1][j]$得来,找上方一格,即$C[5][6]$,此时$C[5][6]=1$,说明该值在最长公共子序列中,即$x_5$在最长公共子序列中,再找左上角,为3,找左边,为3,找左边,为1,说明可输出,找左上角。类推。

最终输出结果$x_2,x_3,x_4,x_5,x_7$,即23489。

注意点

这里我们可以注意到除了23489之外,23469也可以,这点取决于当$C[i-1][j]和C[i][j-1]$相等时取谁。

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
public static int[] Sort(int[] arr) {
int length = arr.length;
for (int i = 0; i < arr.length; i++) {
//每一趟循环比较时,min用于存放较小元素的数组下标,
//这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标,避免每次遇到较小元素都要进行交换。
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
//进行交换,如果min发生变化,则进行交换
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
int i = 0;

//去重
while(i<length-1)
{
if(arr[i] == arr[i+1])
{
for(int j=i;j<length;j++)
{
arr[j]=arr[j+1];
}
length--;
}
else
i++;
}
int []b = new int[length];
for(int j=0;j<length;j++)
{
b[j] = arr[j];
}
return b;
}


/**
* 构建最长公共子序列
* @param i x序列的下标?
* @param j y序列的下标?
* @param x 序列x
* @param b 通过lcsLength()得到的状态数组?
*/
public static void lcs(int i,int j, int[]x,int [][]b)
{
if(i==0 || j == 0) return;
if(b[i][j] == 1)
{
//即第二种情况,X和Y最后一个元素相同
lcs(i-1,j-1,x,b); //递归调用
System.out.print(x[i-1]);
}
else if(b[i][j] == 2)
{
//即第三种情况中的第一种情况,右侧大于左侧
lcs(i-1,j,x,b);
}
else
{
//即第三种情况中的第二种情况,左侧大于右侧
lcs(i,j-1,x,b);
}
}

/**
* P58页,最长公共子序列代码
* @param x 序列X
* @param y 序列Y
* @param b 状态字,用于判断序列满足哪种情况
* @return 返回X和Y的最长公共子序列长度
*/
public static int lcsLength(int[]x,int[]y,int [][]b)
{
int m = x.length;
int n = y.length;
int [][]c = new int[m+1][n+1];

//初始化边界条件
for(int i=0;i<=m;i++)
c[i][0] = 0;
for(int i=0;i<=n;i++)
c[0][i] = 0;

for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(x[i-1] == y[j-1])
{
//第二种情况,即此部分X和Y最后一个元素相同,那么最长公共子序列长度为之前的序列的最长公共子序列的长度+1
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else if(c[i-1][j] >= c[i][j-1])
{
//第三种情况中的第一种,即右侧的最长公共子序列的长度大于左侧,那么X和Y的最长公共子序列长度即为右侧
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
{
//第三种情况中的第二种,即左侧的最长公共子序列的长度大于右侧,那么X和Y的最长公共子序列长度即为左侧
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
return c[m][n];
}

public static void main(String[] args) {
//char []X = {' ','A','B','E','B','D','A','B'};
//char []Y = {'B','D','C','A','B','A'};
//char []X = {'C','B','A'};
//char []Y = new char[X.length];
int []X = {5,2,3,4,8,6,9};
int []Y = new int[X.length];
for(int i=0;i<Y.length;i++)
Y[i]=X[i];
Y = Sort(Y);
int [][]b = new int[X.length+1][Y.length+1];
int x = lcsLength(X,Y,b);
System.out.println(x);
lcs(X.length,Y.length,X,b);
x+=1;
}

Comments

Unable to load Disqus, please make sure your network can access.