加载中…
个人资料
BirdMan
BirdMan
  • 博客等级:
  • 博客积分:0
  • 博客访问:74,611
  • 关注人气:13
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

动态规划中最长公共子序列(LCS)java实现

(2011-04-13 18:05:37)
标签:

最长公共子序列

java

杂谈

动态规划中最长公共子序列中的内容很多,这里不做详细的介绍了,可以找相关的资料,这里得实现的方法,主要是参考《算法导论》,这里介绍LCS的最优子结构的递归式:
c[i][j] = 0  (i = 0 或 j = 0)
c[i][j] = c[i - 1][j - 1] + 1  (i ,j > 0 和 x[i] == y[i])
c[i][j] = max{c[i][j - 1],c[i - 1][j])  (i ,j > 0 和 x[i] <> y[i])

源代码:package chap1;

public class LCS {

int[][] lcsLength(char[] x,char[] y){
int m = x.length;
int n = y.length;
int i,j;
int[][] c = new int[m][n];
int[][] b = new int[m][n];
for(i = 1;i < m;i++)
c[i][0] = 0;
for(j = 0;j < n;j++)
c[0][j] = 0;
for(i = 1;i < m;i++)
for(j = 1;j < n;j++){
if(x[i] == y[j]){
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
}
else if(c[i - 1][j] >= c[i][j - 1]){
c[i][j] = c[i - 1][j];
b[i][j] = 2;
}else{
c[i][j] = c[i][j - 1];
b[i][j] = 3;
}
}
return b;
}
void printLCS(int[][] b,char[] x,int i,int j){
if(i == 0 || j == 0)
return;
if(b[i][j] == 1){
printLCS(b,x,i - 1,j - 1);
System.out.print(x[i] + "\t");
}else if(b[i][j] == 2)
printLCS(b,x,i - 1,j);
else
printLCS(b,x,i,j - 1);
}
public static void main(String[] args) {
char[] x = {' ','A','B','C','B','D','A','B'};
char[] y = {' ','B','D','C','A','B','A'};
LCS lcs = new LCS();
lcs.printLCS(lcs.lcsLength(x, y), x, x.length-1, y.length-1);
}
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有