算法复习周------“动态规划之‘最长公共子序列’”&&《计蒜课》---最长公共子串题解

时间:2024-09-20 20:06:02

问题描述: 这个问题其实很容易理解。就是给你两个序列X={x1,x2,x3......xm} Y={y1,y2,y3......ym},要求找出X和Y的一个最长的公共子序列。

例:Xi={A, B, C, B, D, A}    Yj={B, C, A, B, A}  求得 Z={B, C, B, A}

问题详解: 那么问题来了,我们如何去求解出最终的过程呢?既然是复习周,那我就开门见山,直接用DP算法去解决这个问题。

分析:该问题具有最优子结构的性质。

这里我们使用上面的那个例子:我们此时倒着进行分析

①当我们知道了最长公共子序列为Z={B,C,B,A}的时候,我们知道当取Xi序列的最后一个值x6=A与Yi序列的最后一个值Y5=A,此时X6=Y5,则z4=X6=Y5,就得出来的 Z1~Z3 为 X1~X5 与 Y1~Y4 的最长公共子序列。

②再往前走,X5=D而Y4=B我们知道  x5!=Y4  所以Z1~Z3是  X1~X5 与 Y1~Y3的子序列 或者是 X1~X4 与 Y1~Y4的子序列(这里这个例子是——Z{B,C,B}是A{A,B,C,B}与B{B,C,A,B}的公共子序列)

也许文字不太好理解,但是我们由此可以归纳出一个递推公式:算法复习周------“动态规划之‘最长公共子序列’”&&《计蒜课》---最长公共子串题解

而C[i][j]中存的是序列X1~Xi与序列Y1~Yj的最长公共子序列长度。

下面我们来看具体的寻找方法——>

  这里我们放一道例题:

给定两个序列为X=<A, B, C, B, D, A, B>和 Y=<B, D, C, A, B, A>,求最长公共子序列?

这个时候我们需要递归来填写出数组中的数字。

①我们来画出这个二维数组。

算法复习周------“动态规划之‘最长公共子序列’”&&《计蒜课》---最长公共子串题解

②因为0行0列并没有实际的意义,所以我们填上0。

算法复习周------“动态规划之‘最长公共子序列’”&&《计蒜课》---最长公共子串题解

③之后,我们开始递归写表。此时我们要知道,行数1~7代表X的各个数字,而列为Y的数字。当i=1是代表我拿出来X数列中的A,j=1代表我拿出来Y数列中的B。然后比较发现A!=B  所以我们判断max(C[0][1],C[1][0])--其实我们写算法的时候都默认从上面继承下来。发现都是0,所以C[1][1]=0。

④同样的情况一直到C[1][4]这个地方,此时我们发现X1=A,Y4=A。X1=Y4。所以我们调用C[i][j]=C[i-1][j-1]函数,从左上角继承下来。C[1][4]=C[0][3]=0+1=1。

。。。。。最后填写完成后为:

算法复习周------“动态规划之‘最长公共子序列’”&&《计蒜课》---最长公共子串题解(其实算法思想很简单,就是当前两个数相同就左上角的值+1,不相同就比较左边和上面,找大的写上去)

此时我们就要进入下一步,就是根据这个表去找到最长公共子序列。

而在上面的每一步填写表格的时候,我们需要加上一步——就是记录我当前的这个格子的值是从什么位置继承来的。(创建一个新的二维数组)  这里我们规定:

①当C[i][j]是从左上角+1得来的,我们在b[i][j]处填上1。

②当C[i][j]是从左侧继承来的,b[i][j]=3。

③当C[i][j]从上面继承来的,b[i][j]=2。

我们这里得到b[i][j]

算法复习周------“动态规划之‘最长公共子序列’”&&《计蒜课》---最长公共子串题解

之后我们从最右下角的位置开始,根据b中的表格得到:

算法复习周------“动态规划之‘最长公共子序列’”&&《计蒜课》---最长公共子串题解

这个时候我们取箭头的末端所在行——第2、3、4、6行,对应X序列中的B,C,B,A。由此得到Z序列。

算法代码:

  因为这道题目要考上机题,所以我在这里把代码思想也放到这里,不过代码很简单这里就不详细叙述了

#include<iostream>
#include<string.h>
using namespace std;
int C[][];
int bb[][];
char A[];
int LCS(char a[],char b[],int a_len,int b_len){
for(int i =;i<;i++){
C[][i]=;
C[i][]=;
}
for(int h=;h<=a_len;h++){
for(int hh=;hh<=b_len;hh++){
if(a[h-]==b[hh-]) {
C[h][hh]=C[h-][hh-]+;
bb[h][hh]=;
}
else{
if(C[h-][hh]>=C[h][hh-]) {
C[h][hh]=C[h-][hh];
bb[h][hh]=; }
if(C[h-][hh]<C[h][hh-]){
C[h][hh]=C[h][hh-];
bb[h][hh]=;
}
}
}
}
}
int LCScout(int a,int b){
if(a==||b==) return ;
else{
if(bb[a][b]==) {
LCScout(a-,b-);
cout<<A[a-];
}
if(bb[a][b]==){
LCScout(a-,b);
}
if(bb[a][b]==){
LCScout(a,b-);
}
}
}
int main(){ char B[];
cin>>A;
cin>>B;
int A_len = strlen(A);
int B_len = strlen(B);
LCS(A,B,A_len,B_len);
LCScout(A_len,B_len); }

上面的代码是我自己写着玩的一些寻找最长公共序列的方法,下面我在放上计蒜课上的——《最长共公子串》

#include<iostream>
#include<string.h>
using namespace std;
int lcs[][];
int b[][]; int LCS(char A[],char B[],int a_len,int b_len){
int max=;
for(int i=;i<=;i++){
lcs[][i]=;
lcs[i][]=;
}
for(int i=;i<=a_len;i++){
for(int h=;h<=b_len;h++){
if(A[i-]==B[h-]) {
lcs[i][h]=lcs[i-][h-]+;
if(lcs[i][h]>max) max=lcs[i][h];
b[i][h]=;
}
else{
if(lcs[i-][h]>=lcs[i][h-]){
lcs[i][h]=lcs[i-][h];
b[i][h]=;
}
else{
lcs[i][h]=lcs[i][h-];
b[i][h]=;
}
}
}
}
return max;
}
int main(){
char A[];
char B[];
cin>>A;
cin>>B;
int A_len = strlen(A);
int B_len = strlen(B); cout<<LCS(A,B,A_len,B_len);
}

是不是很基础~相信大家算法考试应该问题不大~加油加油!

——————————————————————————————————————Made By Pinging