动态规划算法-最长公共子序列

亦凉 2022-03-31 13:51 434阅读 0赞

在两个字符串中，有些字符会一样，可以形成的子序列也有可能相等，因此，长度最长的相等子序列便是两者间的最长公共字序列，其长度可以使用动态规划来求。

以s1=\{1,3,4,5,6,7,7,8\},s2=\{3,5,7,4,8,6,7,8,2\}为例。

借用《算法导论》中的推导图：

创建 DP数组C\[\]\[\];

![Center][]

图中的空白格子需要填上相应的数字（这个数字就是c\[i\]\[j\]的定义，记录的LCS的长度值）。填的规则依据递归公式，简单来说：**如果横竖（i,j）对应的两个元素相等，该格子的值 = c\[i-1,j-1\] + 1。如果不等，取c\[i-1,j\] 和 c\[i,j-1\]的最大值。首先初始化该表**：

![Center 1][]

然后，一行一行地从上往下填：

![Center 2][]

S1的元素3 与 S2的元素3 相等，所以 c\[2,1\] = c\[1,0\] + 1。继续填充：

![Center 3][]

S1的元素3 与 S2的元素5 不等，c\[2,2\] =max(c\[1,2\],c\[2,1\])，图中c\[1,2\] 和 c\[2,1\] 背景色为浅黄色。

继续填充：

![Center 4][]

![Center 5][]

![Center 6][]

中间几行填写规则不变，直接跳到最后一行：

![Center 7][]

至此，该表填完。根据性质，c\[8,9\] = S1 和 S2 的 LCS的长度，即为5。

得到公式

![Center 8][]

JAVA代码

package test;
    
    import java.util.Scanner;
    public class test27 {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		System.out.println("请输入第一个字符串:\n");
    		String s1 = sc.nextLine();
    		System.out.println("请输入第二个字符串:\n");
    		String s2 = sc.nextLine();
    		int res = LCSlength(s1,s2);
    		System.out.println(res);
    	}
    	 public static int LCSlength(String str1, String str2) {  
    		    int len1 = str1.length();    
    		    int len2 = str2.length();  
    		    int c[][] = new int[len1+1][len2+1];    //定义二维数组
    		    for (int i = 0; i <= len1; i++) {  
    		        for( int j = 0; j <= len2; j++) {  
    		            if(i == 0 || j == 0) {    //如果两个字符有一个为空，那么最长公共子序列为0
    		                c[i][j] = 0;  
    		            } else if (str1.charAt(i-1) == str2.charAt(j-1)) {  //当Xm = Yn时，找到Xm-1和Yn-1的最长公共子序列的长度，并使长度+1
    		                c[i][j] = c[i-1][j-1] + 1;  
    		            } else {    //如果Xm!=Yn,给此时的c[i][j]赋值为Xm-1和Yn-1中最大的那一个
    		                c[i][j] = max(c[i - 1][j], c[i][j - 1]);  
    		            }  
    		        }  
    		    }  
    		    return c[len1][len2];  
    		}
    public static int max(int i, int j) {
    	return i>=j?i:j;
    	} 
    }

当得到完整的DP表之后，我们可以通过倒推来得到相应的子序列

S1和S2的最LCS并不是只有1个，本文并不是着重讲输出两个序列的所有LCS，只是介绍如何通过上表，输出其中一个LCS。

我们根据递归公式构建了上表，我们将从最后一个元素c\[8\]\[9\]倒推出S1和S2的LCS。

c\[8\]\[9\] = 5，且S1\[8\] != S2\[9\]，所以倒推回去，c\[8\]\[9\]的值来源于c\[8\]\[8\]的值(因为c\[8\]\[8\] > c\[7\]\[9\])。

c\[8\]\[8\] = 5,  且S1\[8\] = S2\[8\], 所以倒推回去，c\[8\]\[8\]的值来源于 c\[7\]\[7\]。

以此类推，如果遇到S1\[i\] != S2\[j\] ，且c\[i-1\]\[j\] = c\[i\]\[j-1\] 这种存在分支的情况，这里请都选择一个方向（之后遇到这样的情况，也选择相同的方向）。

第一种结果为：

![Center 9][]

这就是倒推回去的路径，棕色方格为相等元素，即LCS = \{3,4,6,7,8\}，这是其中一个结果。

如果如果遇到S1\[i\] != S2\[j\] ，且c\[i-1\]\[j\] = c\[i\]\[j-1\] 这种存在分支的情况，选择另一个方向，会得到另一个结果。

![Center 10][]

即LCS =\{3,5,7,7,8\}。

在倒推时，如果s1\[i\] == s2\[j\] 就跳转到c\[i - 1\]\[j - 1\],如果s1\[i\] != s1\[j\], 就向前找或向上找（只能一个方向）

[Center]: /images/20220331/9e88250eb6a5454aada1042f96adda35.png
[Center 1]: /images/20220331/ddbf6f542c37451db031aa4779363d9c.png
[Center 2]: /images/20220331/4fdf688238df4c7b918195303b4f572b.png
[Center 3]: /images/20220331/24c8438f0da64bcba431544e58710cc5.png
[Center 4]: /images/20220331/0e8abc1583a14de5a9c908a91da57bac.png
[Center 5]: /images/20220331/387ebac955124134931037ebcd44d940.png
[Center 6]: /images/20220331/08d358b9c83b4c9c9719402b7082b42f.png
[Center 7]: /images/20220331/43fccee46cef476fa256540909da179f.png
[Center 8]: /images/20220331/2c715f6fcbb8438d9a68e84f74c56b50.png
[Center 9]: /images/20220331/674136ce1d004f2588f3fd5188862ff9.png
[Center 10]: /images/20220331/141f877ef2d24e60bd704db3c341bef6.png