【谈谈】动态规划——求最长公共子序列

素颜马尾好姑娘i 2022-01-31 07:13 257阅读 0赞

首先，我们要搞清楚所谓最长公共子序列的概念。不然很容易把它和最长公共子串混淆，两者区别是：子序列只需要字符保持相对顺序，并不要求像公共字串那样组成字符还需连续。  
问题：  
给定两个字符串数组序列：

X[1...m] = {A, B, C, B, D, A, B}
    Y[1...n] = {B, D, C, A, B, A}

求它们的最长公共子序列，我们可肉眼判断，这两个字符串数组序列的最长公共子序列长度为4.

“BDAB”
    “BCAB”
    “BCBA”

现在用代码解决这个问题，一般人比如说我最容易想到方法都是穷举法：  
列出X的所有子序列，再在Y中找到和其匹配的最长子序列。  
如果用穷举法解决，时间复杂度最多能达到O(n\*2^m)，也就是说，在一些特定场合比如校招面试，使用这种方法极易被pass。  
再接来考虑递推  
问题的核心就是找到X,Y的最长公共子序列，记为LCS(X,Y)。

如果xm = yn，则Ck = xm = yn 且 Ck-1是Xm-1和Yn-1的一个LCS  
如果xm != yn 且 Ck != xm，则C是Xm-1和Y的一个LCS  
如果xm != yn 且 Ck != yn，则C是X和Yn-1的一个LCS  
![在这里插入图片描述][20190521142337791.png]

public class 递归实现 {
        
    	public static int Lcs(char x[],char y[],int i,int j) {
        
    		if(i==0||j==0) {
        
    			return 0;
    		}
    		else if(x[i]==y[j]) {
        
    			return Lcs(x,y,i-1,j-1)+1;
    		}
    		else {
        
    		return Max(Lcs(x,y,i-1,j),Lcs(x,y,i,j-1));
    		}
    	}
    	private static int Max(int a,int b){
        
    	if(a>b) {
        
    		return a;
    	}
    	else {
        
    		return b;
    	}
    	}
    public static void main(String[] args) {
        
    	//System.out.println((int)' ');
    	String s1="ABCBDAB";
    	char[] c1=new char[s1.length()+1];//带0字符的字符数组
    	char[] t1=s1.toCharArray();
    	c1[0]=(char)0;
    	for(int i=1;i<t1.length;i++) {
        
    		c1[i+1]=t1[i];
    	}
    	String s2="BDCABA";
    	char[] c2=new char[s2.length()+1];//带0字符的字符数组
    	char []t2=s2.toCharArray();
    	c2[0]=(char)0;
    	for(int i=1;i<t2.length;i++) {
        
    		c2[i+1]=t2[i];
    	}
    	System.out.println(Lcs(c1,c2,c1.length-1,c2.length-1)) ;
    }
    }

但要是完全用递归求解，在整个二叉树的最有求解过程中，会有大量的重复调用。时间复杂度是指数级，并没有得到太大的优化。所以这里我们建议使用动态规划求解。  
为了杜绝相关不必要重复步骤，我们选择用动态规划求解，通过备忘录或者说一张表来存放数据，避免重复的计算和调用，以空间换时间，同时本问题还符合动态规划的基本特征，求解最优子结构和重复子问题。

备忘录方法采用自顶向下方式,为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解

public class 备忘录法 {
        
    	public static int Lcs(char x[],char y[],int i,int j,int bak[][]) {
        
    		if(bak[i][j]!=-1) {
        
    			return bak[i][j];
    		}
    		if(i==0||j==0) {
        
    			return bak[i][j]=0;
    		}
    		else if(x[i]==y[j]) {
        
    			return Lcs(x,y,i-1,j-1,bak)+1;
    		}
    		else {
        
    	 bak[i][j]=Max(Lcs(x,y,i-1,j,bak),Lcs(x,y,i,j-1,bak));
    		}
    		return bak[i][j];
    	}
    	private static int Max(int a,int b){
        
    	if(a>b) {
        
    		return a;
    	}
    	else {
        
    		return b;
    	}
    	}
    public static void main(String[] args) {
        
    	//System.out.println((int)' ');
    	String s1="ABCBDAB";
    	char[] c1=new char[s1.length()+1];//带0字符的字符数组
    	char[] t1=s1.toCharArray();
    	c1[0]=(char)0;
    	for(int i=1;i<t1.length;i++) {
        
    		c1[i+1]=t1[i];
    	}
    	String s2="BDCABA";
    	char[] c2=new char[s2.length()+1];//带0字符的字符数组
    	char []t2=s2.toCharArray();
    	c2[0]=(char)0;
    	for(int i=1;i<t2.length;i++) {
        
    		c2[i+1]=t2[i];
    	}
    	//初始化备忘录数组
    	int [][]bak=new int[c1.length][c2.length];
    	for(int i=0;i<c1.length;i++) {
        
    		for(int j=0;j<c2.length;j++) {
        
    			bak[i][j]=-1;
    		}
    	}
    	System.out.println(Lcs(c1,c2,c1.length-1,c2.length-1,bak)) ;
    }
    }

备忘录法相比于递归以空间换时间，降低了时间复杂度，但占用内存会大大升高，并且它的时间复杂度相比于下面这种方法并不算太过优化。  
动态规划—自底向上法：  
采用自底向上方式,保存已求解的子问题,需要时取出,消除对某些子问题的重复求解.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]

import java.util.Scanner;
    
    public class 自底向上 {
        
    	public static int Lcs(char x[],char y[],int i,int j,int bak[][]) {
        
    		for(int ii=0;ii<=i;ii++) {
        
    			for(int jj=0;jj<=j;jj++) {
        
    				if(ii==0||jj==0) {
        
    				 bak[ii][jj]=0;
    				}
    				else if(x[ii]==y[jj]) {
        
    				bak[ii][jj]= bak[ii-1][jj-1]+1;
    				}
    				else {
        
    			 bak[ii][jj]=Max(bak[ii-1][jj],bak[ii][jj-1]);
    				}
    			}
    		}
    		
    		return bak[i][j];
    	}
    	private static int Max(int a,int b){
        
    	if(a>b) {
        
    		return a;
    	}
    	else {
        
    		return b;
    	}
    	}
    public static void main(String[] args) {
        
    	Scanner s=new Scanner(System.in);
    	//System.out.println((int)' ');
    	String s1=s.nextLine();
    	char[] c1=new char[s1.length()+1];//带0字符的字符数组
    	char[] t1=s1.toCharArray();
    	c1[0]=(char)0;
    	for(int i=1;i<t1.length;i++) {
        
    		c1[i+1]=t1[i];
    	}
    	String s2=s.nextLine();
    	char[] c2=new char[s2.length()+1];//带0字符的字符数组
    	char []t2=s2.toCharArray();
    	c2[0]=(char)0;
    	for(int i=1;i<t2.length;i++) {
        
    		c2[i+1]=t2[i];
    	}
    	int [][]bak=new int[c1.length][c2.length];
    	
    	System.out.println(Lcs(c1,c2,c1.length-1,c2.length-1,bak)) ;
    }
    }

![在这里插入图片描述][20190521141337244.png]

[20190521142337791.png]: /images/20220131/4ef91fa78e4e4396bafa5e5374f3b51f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]: /images/20220131/8728532fad9648aaaa6fc41a90de53a3.png
[20190521141337244.png]: /images/20220131/087864b0140d4f16994cb17af4bb7dd1.png