求最长公共子序列（动态规划）

た入场券 2022-01-26 03:11 295阅读 0赞

**求最长公共子序列（动态规划）**  
首先弄清楚，最长公共子串与最长公共子序列的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。比如说：A=\{v，2，3，b，5，7\}； B=\{1,B,2,b,5，7，x\}; a1=\{2,b，5，7\}是A、B的最长公共子序列，a2=\{5,7\}是A、B的最长公共子串。

举例：  
s1= \{A, B, C, B, D, A, B\}  
s2 = \{B, D, C, A, B, A\}  
求这两个字符串的最长公共子序列  
a1=\{B,D,A,B\}  
a2=\{B,C,A,B\}  
a3=\{B,C,B,A\}  
长度都为4.  
如果运用穷举法，时间复杂度是O(n\*2^m)，如果原字符串过大，将会导致运算时间过长，所以我们要简化算法，降低复杂度，让它更为简便的得出我们所需要的结果。  
**简化算法：**

*  先得到最长公共子序列的长度 设C\[i,j\]=Lcs(1…i,1…j)
 *  得到解C(n,m)=Lcs(x,y)

如果i=0或者j=0 则 C(i,j)=0  
如果x\[i\]=x\[j\]，则LCS ( x,y ) = 1 + LCS ( i-1,j-1 )。  
如果x\[i\]!=x\[j\]，则LCS( x,y )= max\{ LCS ( i-1, j ), LCS ( i, j-1 ) \}  
递归法：

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;
    			}
    			return b;
    		}
    
    	public static void main(String[] args) {
        	     String s1 ="ABCBDAB";
        	     char[] c1 = new char[s1.length()+1];//带0号字符的字符数组
        	     char[] t1 = s1.toCharArray();//把字符串转变为字符数组
        	     c1[0]= (char)0;//在字符数组前面放一个0号字符
        	     for (int i = 0; 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;//在字符数组前面放一个0号字符
        	     for (int i = 0; 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) 
    	    		 bak[i][j]=0;//存的0到备忘录里
    	    	 else if(x[i]==y[j])
    	    		 return lcs(x, y, i-1, j-1,bak)+1;
    	    	 else 
                     return 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;
    			}
    			return b;
    		}
    
    	public static void main(String[] args) {
        	     String s1 ="ABCBDAB";
        	     char[] c1 = new char[s1.length()+1];//带0号字符的字符数组
        	     char[] t1 = s1.toCharArray();//把字符串转变为字符数组
        	     c1[0]= (char)0;//在字符数组前面放一个0号字符
        	     for (int i = 0; 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;//在字符数组前面放一个0号字符
        	     for (int i = 0; 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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTAzMDAyMw_size_16_color_FFFFFF_t_70]

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++) {//i,j是索引 不是总长度 不需要 -1
    					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;
    			}
    			return b;
    		}
    
    	public static void main(String[] args) {
        	     String s1 ="ABCBDAB";
        	     char[] c1 = new char[s1.length()+1];//带0号字符的字符数组
        	     char[] t1 = s1.toCharArray();//把字符串转变为字符数组
        	     c1[0]= (char)0;//在字符数组前面放一个0号字符
        	     for (int i = 0; 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;//在字符数组前面放一个0号字符
        	     for (int i = 0; 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));
    		
    	}
    }

最后运用回溯法  
算法分析：从最后一个开始找（我们找一条路径举例子），比较x\[i-1\]\[j\]和x\[i\]\[j-1\]如果相同，得到这个公共字符，如果不同取max(lcs(x, y, i-1, j),lcs(x, y, i, j-1));继续走，直到i=0||j=0结束。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTAzMDAyMw_size_16_color_FFFFFF_t_70 1]  
参考：[https://blog.csdn.net/lisonglisonglisong/article/details/41548557][https_blog.csdn.net_lisonglisonglisong_article_details_41548557]  
[https://blog.csdn.net/zhongkeli/article/details/8847694][https_blog.csdn.net_zhongkeli_article_details_8847694]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTAzMDAyMw_size_16_color_FFFFFF_t_70]: /images/20220126/b4fa0b476a324487b6d4579ed0d9354b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTAzMDAyMw_size_16_color_FFFFFF_t_70 1]: /images/20220126/ee9063937e6c42e9bfe8b02a87b2a00e.png
[https_blog.csdn.net_lisonglisonglisong_article_details_41548557]: https://blog.csdn.net/lisonglisonglisong/article/details/41548557
[https_blog.csdn.net_zhongkeli_article_details_8847694]: https://blog.csdn.net/zhongkeli/article/details/8847694