动态规划最长公共子序列（LCS）问题（Java实现）

深碍√TFBOYSˉ_ 2023-02-13 00:24 7阅读 0赞

###  ###

*  动态规划最长公共子序列（LCS）问题（Java实现）
 *   *  问题分析
     *  Java代码实现

# 动态规划最长公共子序列（LCS）问题（Java实现） #

> 首先，明白一个公共子序列和公共子串的区别
> 
>  *  公共子序列： **可以不连续**
>  *  公共子串： **必须连续**

## 问题分析 ##

--------------------

1.  求最长公共子序列，先明白两个概念
    
     *  子序列
        
         *  一个给定序列中删去若干元素后得到的序列
     *  公共子序列
        
         *  给定两个序列X，Y，当另一序列Z 既是X 的子序列，又是Y 的子序列时，就称Z 为X、Y 的**公共子序列**
2.  明白上述两个概念后，我们就可以开始搜索最长公共子序列
    
     *  这个问题可以使用暴力方法解决，但是由于要全部搜索一遍，时间复杂度为 **O(n2m)**，所以我们不采用
     *  我们可以使用动态规划算法，自底向上进行搜索，这样，在计算后面的时候，前面的数据我们已经对其进行保存，直接进行计算即可，时间复杂度很大程度降低。
3.  既然决定使用动态规划算法，首先引入一个二位数组 c\[\]\[\], 记录 x\[i\] 与 y\[j\] 的LCS 的长度，b\[i\]\[j\] 记录 c\[i\]\[j\] 的通过哪一个子问题的值求得的，以决定搜索方向。
4.  抽取状态转移方程（X=x1x2…xm、Y=y1y2…yn为两个序列，Z=z1z2…zk为公共子序列）
    
     *  对于 x\[i\] 和 y\[j\], 若 i = 0 or j = 0，显然，c\[i\]\[j\] = 0
     *  若 i = j，我们可以使用上一步计算的值直接进行计算，即 c\[i\]\[j\] = c\[i-1\]\[j-1\] + 1
     *  若 i ≠ j，有两种情况
        
        1.  Zk ≠ Xm，那么Z 一定是Xm-1, Y 的一个公共子序列,
        2.  Zk ≠ Yn，那么Z 一定是X, Yn-1 的一个公共子序列
     *  这样，第三种情况我们就可以表示成： c\[i\]\[j\] = max\{c\[i-1\]\[j\], c\[i\]\[j-1\]\}
     *  那么，我们就可以写出其状态转移方程

c \[ i \] \[ j \] = \{ 0 i = 0 ， o r ， j = 0 c \[ i − 1 \] \[ j − 1 \] + 1 x \[ i \] = y \[ j \] m a x c \[ i − 1 \] \[ j \] , c \[ i \] \[ j − 1 \] x \[ i \] ≠ y \[ j \] c\[i\]\[j\] = \\begin\{cases\} 0 & i = 0，or， j = 0 \\\\ c\[i-1\]\[j-1\] + 1 & x\[i\] = y\[j\] \\\\ max\{c\[i-1\]\[j\], c\[i\]\[j-1\]\} & x\[i\] ≠ y\[j\] \\end\{cases\} c\[i\]\[j\]=⎩⎪⎨⎪⎧0c\[i−1\]\[j−1\]\+1maxc\[i−1\]\[j\],c\[i\]\[j−1\]i=0，or，j=0x\[i\]=y\[j\]x\[i\]=y\[j\]

## Java代码实现 ##

/* * 若尘 */
    package lsc;
    
    /** * 最长公共子序列 * @author ruochen * @version 1.0 */
    public class LSCProblem { 
    	
    		/** lcs 用来保存最优解 */
    		private static String lcs = "";
    
    	public static void main(String[] args) { 
    		String str1 = "ABCDBC";
    		String str2 = "ABCEAC";
    		
    		String[] x = strToArray(str1);
    		String[] y = strToArray(str2);
    		
    		int[][] b = getSearchRoad(x, y);
    		
    		Display(b, x, x.length - 1, y.length - 1);
    		System.out.println("lcs： " + lcs);
    		System.out.println("len: " + lcs.length());
    	}
    	
    	
    	/** * * @param str * @return */
    	public static String[] strToArray(String str) { 
    		String[] strArray = new String[str.length() + 1];
    		strArray[0] = "";
    		for (int i = 1; i < strArray.length; i++) { 
    			strArray[i] = ""+str.charAt(i - 1);
    		}
    		return strArray;
    	}
    	
    	/** * 计算最长子序列长度以及记录最优解数组 * @param x 序列1 * @param y 序列2 * @return 返回一个可查询最优解的数组 */
    	public static int[][] getSearchRoad(String[] x, String[] y) { 
    		int[][] b = new int[x.length][y.length];
    		int[][] c = new int[x.length][y.length];
    		
    		// 第一行 or 第一列，x[i] or y[j] 为0, 对应 c[i][j] 赋值为0 
    		for (int i = 0; i < x.length; i++) { 
    			c[i][0] = 0;
    		}
    		for (int j = 0; j < y.length; j++) { 
    			c[0][j] = 0;
    		}
    		for (int i = 1; i < x.length; i++) { 
    			for (int j = 1; j < y.length; j++) { 
    				if (x[i].equals(y[j])) { 
    					c[i][j] = c[i-1][j-1] + 1;
    					// b[i][j] = 1 表示取决于左上方
    					b[i][j] = 1;
    				} else if (c[i-1][j] >= c[i][j-1]) { 
    					// 此处因为还要记录b[i][j]，所以没有使用max函数
    					c[i][j-1] = c[i-1][j];
    					// b[i][j] = 0 表示取决于左边
    					b[i][j] = 0;
    				} else { 
    					c[i][j] = c[i][j-1];
    					// b[i][j] = -1 表示取决于上边
    					b[i][j] = -1;
    				}
    			}
    		}
    		return b;
    	}
    	
    	/** * 自右下向左上回溯，输出最优解 * @param b * @param x * @param i * @param j */
    	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);
    			lcs += 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);
    		}
    	}
    	
    	/** * 返回两个数的较大值 * @param x 第一个数 * @param y 第二个数 * @return */
    	/* public static int max(int x, int y) { return (x >= y) ? x : y; } */
    }