Java （动态规划算法）解决最长公共子序列问题

最长公共子序列问题：

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

下面的代码计算的是，两个数组的最长公共子序列。

代码如下：

package 实验测试;


import java.util.Scanner;


public class LCSS {
	public static void main(String args[]) {
		int n,m;
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		m = scanner.nextInt();
		int a[] = new int [m];
		int b[] = new int [n];
		int w = n+1;
		int y = m+1;
		int c[][] = new int [w][y];
		int d[][] = new int [m][n];
		//使用随机数来产生数组中的元素
		for(int i = 0; i < a.length; i++) {
			a[i] = (int)(Math.random()*10);
		}
		System.out.print("第一个数组为：");
		for(int i = 0; i < a.length; i++) {
			System.out.print(a[i]+"  ");
		}
		System.out.println();
		for(int j = 0; j < b.length; j++) {
			b[j] = (int)(Math.random()*10);
		}
		System.out.print("第二个数组为：");
		for(int i = 0; i < a.length; i++) {
			System.out.print(b[i]+"  ");
		}
		System.out.println();
        System.out.print("最长公共子序列为：");
		LCSlength lcs = new LCSlength();
		lcs.LCS(a, b, c, d);
		lcs.LCS1(m-1, n-1, a, d);
	}
}

class LCSlength{
	void LCS(int a[],int b[],int c[][],int d[][]) {
		int i ,j;
	       for (i = 1; i < a.length; i++) c[i][0] = 0;
	       for (i = 1; i < b.length; i++) c[0][i] = 0;
	       for (i = 1; i < a.length; i++)
	          for (j = 1; j < b.length; j++)
	          {
	            if (a[i]==b[j])
	            {
	                 c[i][j]=c[i-1][j-1]+1;
	                 d[i][j]=1;
	            }
	            else if (c[i-1][j]>=c[i][j-1])
	            {
	                 c[i][j]=c[i-1][j];
	                 d[i][j]=2;
	            }
	            else
	            {    c[i][j]=c[i][j-1];
	                 d[i][j]=3;
	            }
	         }

	}
	void LCS1(int i,int j,int a[],int d[][]) {

		if (i ==0 || j==0) return;
	      if (d[i][j]== 1)
	      {
	           LCS1(i-1,j-1,a,d);
	           System.out.print(a[i]+"  ");
	      }
	      else if (d[i][j]== 2)
	           LCS1(i-1,j,a,d);
	      else LCS1(i,j-1,a,d);

	}
}

运行截图如下：