这是算法导论动态规划一章讲的内容。
public class LCSProblem
{
public static void main(String[] args)
{
String[] x = {"", "A", "B", "C", "B", "D", "A", "B"};
String[] y = {"", "B", "D", "C", "A", "B", "A"};
int[][] b = getLength(x, y);
Display(b, x, x.length-1, y.length-1);
}
public static int[][] getLength(String[] x, String[] y)
{
int[][] b = new int[x.length][y.length];
int[][] c = new int[x.length][y.length];
for(int i=1; i<x.length; i++)
{
for(int j=1; j<y.length; 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] = 0;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = -1;
}
}
}
return b;
}
public static void Display(int[][] b, String[] x, int i, int j)
{
if(i == 0 || j == 0)
return;
if(b[i][j] == 1)
{
Display(b, x, i-1, j-1);
System.out.print(x[i] + " ");
}
else if(b[i][j] == 0)
{
Display(b, x, i-1, j);
}
else if(b[i][j] == -1)
{
Display(b, x, i, j-1);
}
}
}
分享到:
相关推荐
由此函数,把序列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),...
java解决动态规划中最长公共子序列(longest common sequence)问题
关于动态规划算法的最长公共子序列的Java代码,帮助了解算法实现过程
最长公共子序列问题 基于java实现动态规划求解最长公共子序列问题
LCS 最长公共子序列 用JAVA实现,直接导入可运行,实例可以另外自己定义
最长公共子序列问题 Java动态规划求解最长公共子序列问题.zip
java算法分析与设计之最长公共子序列问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的...
主要介绍了Java基于动态规划法实现求最长公共子序列及最长公共子字符串,简单描述了动态规划法的概念、原理,并结合实例形式分析了Java使用动态规划法求最长公共子序列以及最长公共子字符串相关实现技巧,需要的朋友...
最长公共子序列问题 基于Java+动态规划算法解决最长公共子序列问题
所有最长公共子序列(LCS)——动态规划——Java---所有!!!所有!!!所有!!!
最长公共子序列问题 使用Java实现的计算两字符串相似度+最长公共子序列
LCS算法的简单java实现,可以一起讨论学习
动态规划解决最长公共子序列问题java代码
算法导论中求最长公共子序列Java实现版
【作品名称】:基于 java计算两字符串相似度和最长公共子序列 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【项目介绍】:基于 ...
快速排序算法,求最长公共子序列,0-1背包问题的回溯法求解与分支限界法求解,贪心算法的活动安排问题。都是利用JAVA编程语言实现
最长不升公共子序列问题的动态规划算法,结果求出了子序列的长度以及该子序列是什么,采用的是Java。