DP方式求解:
#include <iostream>
using namespace std;
/**
* 问题描述:两个字符串,求解他们的最长公共子序列,子序列不要求连续
*
* 分析这个问题,我们可以发现有子结构,可以将X,Y两个字符串的最长公共子串
* 的问题转换成更小的子问题。而且这个问题的求解过程有重叠子问题。根据这两个
* 性质我们确定尝试用DP来解决。
* 首先定义状态,f(m,n),代表字符串X以Xm结尾的子串与字符串Y以Yn结尾的子串的
* 最长公共子序列。
* 如果Xm == Yn,那么问题转换成求解f(m-1,n-1),且f(m,n) = f(m-1,n-1)+1
* 如果Xm != Yn,那么最长公共子序列要么是X(m-1)结尾的子串与Yn结尾的子串的最长公共子序列
* 要么是Xm结尾的子串与Y(n-1)结尾的子串的最长公共子序列
* 根据上面分析很容易写出状态转移方程(递推式):
* f(m,n) =
* f(m,n) = f(m-1,n-1)+1. Xm == Yn
* f(m,n) = max{f(m,n-1),f(m-1,n)}. Xm != Yn
*
* 下面代码的任务就是自底向上求解这个状态转移方程。
*/
#define M 8 //行
#define N 7 //列
int dp[M][N] = {0};
int lcs_max(int x, int y){
return x>y?x:y;
}
/**
* DP求解最长公共子序列
*/
int lcs(const char *a, const char *b){
int row = M;
int col = N;
//初始化第一行和第一列
if(a[0] == b[0]) dp[0][0] = 1;
else dp[0][0] = 0;
for(int i=1;i<N;i++){
if(a[0] == b[i]) dp[0][i] = 1;
else dp[0][i] = 0;
}
for(int j=1;j<M;j++){
if(b[0] == a[j]) dp[j][0] = 1;
else dp[j][0] = 0;
}
//核心代码:自底向上求解DP矩阵(注意a是列,b是行)
for(i=1;i<row;i++){
for(j=1;j<col;j++){
if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = lcs_max(dp[i-1][j], dp[i][j-1]);
}
}
//输出lcs矩阵
for(i=0;i<row;i++){
for(j=0;j<col;j++){
cout<<dp[i][j];
}
cout<<endl;
}
//返回最长子序列值
return dp[row-1][col-1];
}
int main(){
char *a = "aceddbcs"; //a作为DP矩阵的列(故DP矩阵8行)
char *b = "cebsdbc"; //b作为DP矩阵的行(故DP矩阵7列)
cout<<lcs(a,b)<<endl;
return 0;
}
分享到:
相关推荐
最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和Y的一个最长公共子序列。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据...
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
C++求最长公共子序列!实用 花费了好长时间!!
1. 最长公共子序列 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=, x2,…, xm>,则另一序列Z=, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 , i2,…, ik>,使得...
利用动态规划 实现排序 找到最长公共工子序列
动态规划的一个计算两个序列的最长公共子序列的方法如下: 以两个序列 X、Y 为例子: 设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[1][1] = same(1,1); f[i,j] = max{f[i-1...
动态规划的一个计算两个序列的最长公共子序列的方法如下: 以两个序列 X、Y 为例子: 设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[1][1] = same(1,1); f[i,j] = max{f[i-1...
用动态规划求最长公共子序列: 问题:求给定两个序列的最长公共子序列,要求输入两个序列,输出它们的最长公共子序列及其长度值。
给定两个序列X={X1, X2,···,Xm}和Y={Y1, Y2,···,Yn},找出X和Y的最长公共子序列(Longest Common Sequence)。 比如字符串X:{BDCABA};字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共...
由此函数,把序列X={x1,x2….xm}和Y={y1,y2…ym}的最长公共子序列的搜索分为M个阶段,第1阶段,按照式1计算X1和Yj的最长公共子序列长度L[1][j](1),第2阶段,按照2式计算X2和Yj的最长公共子序列长度L[2][j](1),...
求两个字符串的最长公共子序列.pdf
最长公共子序列,求两个字符串的最长公共子序列。
动态规划的经典问题,求两个序列的最长公共子序列
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X= { x1, x2,…, xm},则另一序列Z=...给定两个序列X= {x1, x2, …, xm}和Y= {y1, y2, … , yn},要求找出X和Y的一个最长公共子序列。
求最长公共子序列问题(LCS/c++) 两个序列,求解两个序列中最长公共的子序列
输入两个字符串 求解最长公共子序列并输出子序列及长度
最长公共子序列问题,用C#实现的动态规划算法 X=ABCBDAB Y=BDCABA 以上是示例用的测试数据,输入数据可以得到结果
求两个字符串序列的最长公共子序列,利用动态规划求出最优解。