一个给定序列的子序列是在该序列中删去若干元素后得到的序列。若给定序列X={x1, x2, ..., xm},则另一序列Z={z1, z2, ..., zk},X的子序列是指存在一个严格递增下标序列i, 使得对于所用的j=1, 2, 3,...,k有zj = xi.
例如:序列X={A, B, C, B, D, A, B}的一个子序列Z={B, C, D, A}。
给定两个序列X和Y, 当另一序列Z既是X的子序列又是Y的子序列,则称Z为X和Y的公共子序列。
最长公共子序列问题:
给定两个序列X={x1,x2,x3,...,xm}和Y={y1,y2,y3,...,yn},找出X和Y的最长公共子序列
动态规划法:
/*
* 问题描述: 给定两个序列X={x1,x2,x3,...,xm}和Y={y1,y2,y3,...,yn},找出X和Y的最长公共子序列
* 算法分析:最长公共子序列问题具有最优子结构性质和子问题重叠性质,动态规划法解决
* 最优值的递归关系:
* 用c[i][j]记录序列Xi和Yj的最长公共子序列长度
* 分析:
* 1)c[i][j] = 0 i = 0, j = 0;
* 2)c[i][j] = c[i-1][j-1] + 1 xi = xj;
* 3)c[i][j] = max{c[i-1][j], c[i][j-1]} xi != xj
*
* auther:cm
* date:2010/11/17
*
*/
public class LcsLength
{
private char[] arrX;
private char[] arrY;
private int[][] c;
public LcsLength(String arr1, String arr2)
{
arrX = new char[arr1.length() + 1];
arrY = new char[arr2.length() + 1];
System.arraycopy(arr1.toCharArray(), 0, arrX, 1, arr1.length());
System.arraycopy(arr2.toCharArray(), 0, arrY, 1, arr2.length());
//调用函数
lcsLength();
}
//计算最长公共子序列
public void lcsLength()
{
c = new int[arrX.length][arrY.length];
for (int i = 1; i < arrX.length; i++)
{
for (int j = 1; j < arrY.length; j++)
{
if (arrX[i] == arrY[j])
{
c[i][j] = c[i-1][j-1] + 1;
}
else
{
c[i][j] = max(c[i-1][j], c[i][j-1]);
}
}
}
}
private int max(int m, int n)
{
return m > n ? m : n;
}
//返回最长子序列
public String getLCS()
{
String lcs = "";
int i = arrX.length - 1;
int j = arrY.length - 1;
while (i >= 1 && j >= 1)
{
if (arrX[i] == arrY[j])
{
lcs = arrX[i] + lcs;
i--;
j--;
}
else
{
if (c[i][j-1] > c[i-1][j])
{
j--;
}
else
{
i--;
}
}
}
return lcs;
}
public static void main(String[] args)
{
LcsLength lcs = new LcsLength("ABCBDAB", "BDCABA");
System.out.println(lcs.getLCS());
}
}
X={A, B, C, B, D, A, B}, Y={B, D, C, A, B, A}.
执行结果:
BCBA
分享到:
相关推荐
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
用Python实现动态规划中最长公共子序列和最长公共子串问题!
利用动态规划 实现排序 找到最长公共工子序列
算法与数据结构实验报告
最长公共子序列(动态规划) 实验数据:input.txt X={A,B,C,B,D,A,B}; Y={B,D,C,A,B,A} ——要求给出X、Y的最长公共子序列Z,程序运行结束时,将计算结果输出到文件output.txt中。输出文件中包含问题的答案:找不到...
关于动态规划求解最长公共子序列的方法,讲得蛮清楚的。
1. 要求按动态规划法原理求解问题; 2. 两个序列数据通过键盘输入; 3. 要求显示结果。
动态规划求解最长公共子序列问题 动态规划求解最长公共子序列问题 动态规划求解最长公共子序列问题 动态规划求解最长公共子序列问题
C#实现-动态规划-最长公共子序列-DPLCS,根据动态规划的思想实现对最长公共子序列的求解。
利用动态规划求最长公共子序列: #include #include #include #define MAXLEN 100 void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]) { int i, j; for(i = 0; i ; i++) c...
计算机算法设计与分析中有关动态规划最长公共子序列
动态规划中的最长公共子序列PPT课件.pptx
动态规划解决最长公共子序列问题,即寻找两个序列中公共的序列中的最长的那个,结果不唯一,只能输出一个最长公共子序列,并不能生成所有的; 可视化多文档,手动输入两个子序列,显示动态规划算法的解决表格,箭头...
计算机算法设计与分析题目解答,最长公共子序列的动态规划解法
算法导论实验 最长公共子序列程序源码 实验报告
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中, Xi={x1,x2,…,xi};
这是用动态规划算法求解给定的两个序列的最长公共子序列的C++程序。
哈工大算法实验二,最长公共子序列问题,动态规划解决LCS 1.实现基于优化子结构的递归求解算法 2.实现基于动态规划的求解算法 3.实现三个字符串最长公共子序列的动态规划算法 4.有界面源代码和实验报告!均为自己所...
算法分析实验:动态规划法求最长公共子序列及其01背包
java解决动态规划中最长公共子序列(longest common sequence)问题