最长公共子序列

原创

动态规划解最长公共子序列问题

设序列一的序列为：Ai（1<=i<=n）

序列二的序列为：Bj（1<=j<=m）

最长公共子序列为：Ck（1<=k<=z）

能用动态规划解的题目都是可以将原规模的题分解成子问题规模，公共子序列问题可以这样分解：

如果存在An==Bm==Cz，则Ai（1<=i<=n-1）和Bj（1<=j<=m-1）的最长公共子序列为：Ck（1<=k<=z-1）

如果存在An！=Bm，且An！=Cz，则Ai（1<=i<=n-1）和Bj（1<=j<=m）的最长公共子序列为：Ck（1<=k<=z）

如果存在An!=Bm，且Bm！=Cz，则Ai（1<=i<=n）和Bj（1<=j<=m-1）的最长公共子序列为：Ck（1<=k<=z）

利用上述的关系式我们自顶向下的求最长公共子序列长度。

设数组F[ i ][ j ]表示序列一的长度为i，序列二的长度为j时的最长公共子序列长度，显而易见，当i==0或者j==0时，

即存在其中一个序列没有元素时，F[i][j]都是0，然后利用上述的关系式可以继续往下求。

当A[i]==B[j]时，F[i][j]=F[i-1][j-1]

当A[i-1]！=B[j]时，max{ F[i][j-1]，F[i-1][j] }

上面为什么要选出一个最大的呢？

假如是An！=Bm，且An！=Cz这种情况，我们可以知道应该铲除Ai的最后一个元素An，公共子序列长度和原规模

问题的公共子序列长度是相同的，但是如果铲除了Bm，则公共子序列长度肯定会小于等于原规模的公共子序列长度。

为什么会小于等于自己理解了！

 1 import java.util.Scanner;
 2 
 3 public class 算法分析与设计3_1 {
 4     
 5     static void LCS(int m,int n,int A[],int b[][]){
 6         if(m==0 || n==0)return;
 7         if(b[m][n]==1){
 8             LCS(m-1,n-1,A,b);
 9             System.out.print(A[m]+" ");
10         }else if(b[m][n]==2){
11             LCS(m-1,n,A,b);
12         }else{
13             LCS(m,n-1,A,b);
14         }
15     }
16 
17     static void LCSLength(int A[],int B[],int C[][],int m,int n,int b[][]){
18         for(int i=0;i<=m;i++){
19             C[i][0]=0;    //B序列无元素 
20         }
21         for(int i=0;i<=n;i++){
22             C[0][i]=0;    //A序列无元素
23         }
24         for(int i=1;i<=m;i++){
25             for(int j=1;j<=n;j++){
26                 if(A[i]==B[j]){
27                     C[i][j]=C[i-1][j-1]+1;
28                     b[i][j]=1;    //斜上方 
29                 }else if(C[i-1][j]>=C[i][j-1]){
30                     C[i][j]=C[i-1][j];
31                     b[i][j]=2;    //上一行 
32                 }else{
33                     C[i][j]=C[i][j-1];
34                     b[i][j]=3;    //上一列 
35                 }
36             } 
37         }
38         LCS(m,n,A,b);
39     }
40 
41     public static void main(String[] args) {
42         Scanner reader=new Scanner(System.in);
43         int A[]=new int[1000];
44         int B[]=new int[1000];
45         int C[][]=new int[1000][1000];
46         int b[][]=new int[1000][1000];
47         System.out.print("输入第一个序列的大小：");
48         int A_size=reader.nextInt();
49         System.out.print("输入第一个序列的值：");
50         for(int i=1;i<=A_size;i++){
51             A[i]=reader.nextInt();
52         }
53         System.out.print("输入第二个序列的大小：");
54         int B_size=reader.nextInt();
55         System.out.print("输入第二个序列的值：");
56         for(int i=1;i<=B_size;i++){
57             B[i]=reader.nextInt();
58         }
59         System.out.print("最长公共子序列为：");
60         LCSLength(A,B,C,A_size,B_size,b);
61         System.out.println("长度为："+C[A_size][B_size]);
62         reader.close();
63     }
64 
65 }

10:34:09

2018-10-28