精华内容
下载资源
问答
  • 动态规划 最长公共子序列 过程图解

    万次阅读 多人点赞 2016-05-29 22:54:25
     首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后...

    1.基本概念

          首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后得到的结果。什么是子串呢?给定串中任意个连续的字符组成的子序列称为该串的子串。给一个图再解释一下:


           如上图,给定的字符序列: {a,b,c,d,e,f,g,h},它的子序列示例: {a,c,e,f} 即元素b,d,g,h被去掉后,保持原有的元素序列所得到的结果就是子序列。同理,{a,h},{c,d,e}等都是它的子序列。
           它的字串示例:{c,d,e,f} 即连续元素c,d,e,f组成的串是给定序列的字串。同理,{a,b,c,d},{g,h}等都是它的字串。

            这个问题说明白后,最长公共子序列(以下都简称LCS)就很好理解了。
    给定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2},s1和s2的相同子序列,且该子序列的长度最长,即是LCS。
    s1和s2的其中一个最长公共子序列是 {3,4,6,7,8}

    2.动态规划

           求解LCS问题,不能使用暴力搜索方法。一个长度为n的序列拥有 2的n次方个子序列,它的时间复杂度是指数阶,太恐怖了。解决LCS问题,需要借助动态规划的思想。
           动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。

    3.特征分析

           解决LCS问题,需要把原问题分解成若干个子问题,所以需要刻画LCS的特征。

           设A=“a0,a1,…,am”,B=“b0,b1,…,bn”,且Z=“z0,z1,…,zk”为它们的最长公共子序列。不难证明有以下性质:
           如果am=bn,则zk=am=bn,且“z0,z1,…,z(k-1)”是“a0,a1,…,a(m-1)”和“b0,b1,…,b(n-1)”的一个最长公共子序列;
           如果am!=bn,则若zk!=am,蕴涵“z0,z1,…,zk”是“a0,a1,…,a(m-1)”和“b0,b1,…,bn”的一个最长公共子序列;
           如果am!=bn,则若zk!=bn,蕴涵“z0,z1,…,zk”是“a0,a1,…,am”和“b0,b1,…,b(n-1)”的一个最长公共子序列。

           有些同学,一看性质就容易晕菜,所以我给出一个图来让这些同学理解一下:


           以我在第1小节举的例子(S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}),并结合上图来说:

           假如S1的最后一个元素 与 S2的最后一个元素相等,那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS  再加上 S1和S2相等的最后一个元素。

           假如S1的最后一个元素 与 S2的最后一个元素不等(本例子就是属于这种情况),那么S1和S2的LCS就等于 : {S1减去最后一个元素} 与 S2 的LCS, {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。

    4.递归公式

            第3节说了LCS的特征,我们可以发现,假设我需要求 a1 ... am 和 b1 .. b(n-1)的LCS 和 a1 ... a(m-1) 和 b1 .. bn的LCS,一定会递归地并且重复地把如a1... a(m-1) 与 b1 ... b(n-1) 的 LCS 计算几次。所以我们需要一个数据结构来记录中间结果,避免重复计算。

            假设我们用c[i,j]表示Xi 和 Yj 的LCS的长度(直接保存最长公共子序列的中间结果不现实,需要先借助LCS的长度)。其中X = {x1 ... xm},Y ={y1...yn},Xi = {x1 ... xi},Yj={y1... yj}。可得递归公式如下:

             

    5.计算LCS的长度

           这里我不打算贴出相应的代码,只想把这个过程说明白。还是以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。我们借用《算法导论》中的推导图:


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

             

              然后,一行一行地从上往下填:

             

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

              

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

                继续填充:

                

                

                 

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

                  

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

    6.构造LCS

           本文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] 这种存在分支的情况,这里请都选择一个方向(之后遇到这样的情况,也选择相同的方向)。

           第一种结果为:

           

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

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

              

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

    7.关于时间复杂度

            构建c[i][j]表需要Θ(mn),输出1个LCS的序列需要Θ(m+n)。


              本文内容参考如下:

            【1】http://baike.baidu.com/link?url=iKrtEZXAQ3LeQLL7Z0HQWpy7EO7BZInUR17C63lAIDFBJ_COm8e3KmKVxQCD6DlOvji2F9W6achz49Z_anZCfa

            【2】《算法导论》第3版 15.4节


            注意:
            如您发现本文档中有明显错误的地方,
            或者您发现本文档中引用了他人的资料而未进行说明时,请联系我进行更正。
            转载或使用本文档时,请作醒目说明。
            必要时请联系作者,否则将追究相应的法律责任。

            note:
            If you find this document with any error ,
            Or if you find any illegal citations , please contact me correct.
            Reprint or use of this document,Please explain for striking. 
            Please contact the author if necessary, or they will pursue the corresponding legal responsibility.



    展开全文
  • 计算机算法设计与分析中有关动态规划最长公共子序列
  • 动态规划 最长公共子序列

    问题:
    什么是最长公共子序列呢?好比一个数列S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则S称为已知序列的最长公共子序列。

    举个例子,如:有两条随机序列,如 1 3 4 5 5 ,2 4 5 5 7 6,则它们的最长公共子序列便是:4 5 5。

    分析:

    • 最长公共子序列的结构
      最长公共子序列的结构有如下表示:
      设序列X = < x1, x2, …, xm>和Y = < y1, y2, …, yn>的一个最长公共子序列Z = < z1, z2, …, zk>,则:

      1. 若xm = yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列;
      2. 若xm ≠ yn且zk ≠ xm ,则Z是Xm-1和Y的最长公共子序列;
      3. 若xm ≠ yn且zk ≠ yn ,则Z是X和Yn-1的最长公共子序列。

      其中Xm-1=< x1, x2, …, xm-1>,Yn-1=< y1, y2, …, yn-1>,Zk-1=< z1, z2, …, zk-1>。

    • 子问题的递归结构
      由最长公共子序列问题的最优子结构性质可知,要找出X=< x1, x2, …, xm>和Y=< y1, y2, …, yn>的最长公共子序列,可按以下方式递归地进行:

      1. 当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。
      2. 当xm≠yn时,必须解两个子问题,即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。

      由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如,在计算X和Y的最长公共子序列时,可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题,即计算Xm-1和Yn-1的最长公共子序列。

      与矩阵连乘积最优计算次序问题类似,我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=< x1, x2, …, xi>,Yj=< y1, y2, …, yj>。当i=0或j=0时,空序列是Xi和Yj的最长公共子序列,故c[i,j]=0。其他情况下,由定理可建立递归关系。

    求解:

    #include <cstdio>    
    #include <iostream>    
    #include <algorithm>    
    #include <string>    
    using namespace std;    
    
    int main()    
    {    
        string str1,str2;    
        int dp[200][200];    
    
        while(cin>>str1>>str2)    
        {    
            memset(dp,0,sizeof(dp));    
    
            int la = str1.length();    
            int lb = str2.length();    
    
            for(int i = 1; i <= la; i++)    
                for(int j = 1; j <= lb; j++)    
                {    
                    if(str1[i - 1] == str2[j - 1])    
                    {    
                        dp[i][j] = dp[i-1][j-1]+1;    
                    }    
                    else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);    
                }   
    
            cout<<dp[la][lb]<<endl;    
        }    
        return 0; 
    }

    转自:http://blog.csdn.net/u013445530/article/details/45645307

    展开全文
  • 动态规划最长公共子序列(LCS)问题(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[i1][j1]+1maxc[i1][j],c[i][j1]i=0orj=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; 
    	}
    	*/
    }
    
    
    展开全文
  • 最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。一个数列 ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则称为已知序列的最长...
  • java解决动态规划最长公共子序列(longest common sequence)问题
  • 三个cpp文件分别实现 动态规划最长公共子序列,分治法实现最近点对问题,最佳调度问题的回溯
  •  首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后...

    1.基本概念

          首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后得到的结果。什么是子串呢?给定串中任意个连续的字符组成的子序列称为该串的子串。给一个图再解释一下:

           如上图,给定的字符序列: {a,b,c,d,e,f,g,h},它的子序列示例: {a,c,e,f} 即元素b,d,g,h被去掉后,保持原有的元素序列所得到的结果就是子序列。同理,{a,h},{c,d,e}等都是它的子序列。
           它的字串示例:{c,d,e,f} 即连续元素c,d,e,f组成的串是给定序列的字串。同理,{a,b,c,d},{g,h}等都是它的字串。

            这个问题说明白后,最长公共子序列(以下都简称LCS)就很好理解了。
    给定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2},s1和s2的相同子序列,且该子序列的长度最长,即是LCS。
    s1和s2的其中一个最长公共子序列是 {3,4,6,7,8}

    2.动态规划

           求解LCS问题,不能使用暴力搜索方法。一个长度为n的序列拥有 2的n次方个子序列,它的时间复杂度是指数阶,太恐怖了。解决LCS问题,需要借助动态规划的思想。
           动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。

    3.特征分析

           解决LCS问题,需要把原问题分解成若干个子问题,所以需要刻画LCS的特征。

           设A=“a0,a1,…,am”,B=“b0,b1,…,bn”,且Z=“z0,z1,…,zk”为它们的最长公共子序列。不难证明有以下性质:
           如果am=bn,则zk=am=bn,且“z0,z1,…,z(k-1)”是“a0,a1,…,a(m-1)”和“b0,b1,…,b(n-1)”的一个最长公共子序列;
           如果am!=bn,则若zk!=am,蕴涵“z0,z1,…,zk”是“a0,a1,…,a(m-1)”和“b0,b1,…,bn”的一个最长公共子序列;
           如果am!=bn,则若zk!=bn,蕴涵“z0,z1,…,zk”是“a0,a1,…,am”和“b0,b1,…,b(n-1)”的一个最长公共子序列。

           有些同学,一看性质就容易晕菜,所以我给出一个图来让这些同学理解一下:

           以我在第1小节举的例子(S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}),并结合上图来说:

           假如S1的最后一个元素 与 S2的最后一个元素相等,那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS  再加上 S1和S2相等的最后一个元素。

           假如S1的最后一个元素 与 S2的最后一个元素不等(本例子就是属于这种情况),那么S1和S2的LCS就等于 : {S1减去最后一个元素} 与 S2 的LCS, {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。

    4.递归公式

            第3节说了LCS的特征,我们可以发现,假设我需要求 a1 ... am 和 b1 .. b(n-1)的LCS 和 a1 ... a(m-1) 和 b1 .. bn的LCS,一定会递归地并且重复地把如a1... a(m-1) 与 b1 ... b(n-1) 的 LCS 计算几次。所以我们需要一个数据结构来记录中间结果,避免重复计算。

            假设我们用c[i,j]表示Xi 和 Yj 的LCS的长度(直接保存最长公共子序列的中间结果不现实,需要先借助LCS的长度)。其中X = {x1 ... xm},Y ={y1...yn},Xi = {x1 ... xi},Yj={y1... yj}。可得递归公式如下:

             

    5.计算LCS的长度

           这里我不打算贴出相应的代码,只想把这个过程说明白。还是以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。我们借用《算法导论》中的推导图:

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

             

              然后,一行一行地从上往下填:

             

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

              

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

                继续填充:

                

                

                 

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

                  

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

    6.构造LCS

           本文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] 这种存在分支的情况,这里请都选择一个方向(之后遇到这样的情况,也选择相同的方向)。

           第一种结果为:

           

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

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

              

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

    7.关于时空复杂度

            构建c[i][j]表时间需要Θ(mn),空间需要n^2,输出1个LCS的序列需要Θ(m+n)。

    8.程序代码如下:

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int MAX_N = 100010;
    int s1[MAX_N];
    int s2[MAX_N];
    int lcs[10000][10000];
    int main(){
        int n;
        cin >> n;
        for(int i = 0; i < n; i++){
            scanf("%d",&s1[i]);
        }
        for(int i = 0; i < n; i++){
            scanf("%d",&s2[i]);
        }
        for(int i = 0; i < n; i++){
            for(int j = 0;j < n; j++){
                if(i == 0 || j == 0){
                    lcs[i][j] = 0;
                }
                if(s1[i] == s2[j]){
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                }
                else{
                    lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
                }
            }
        }
        printf("%d\n",lcs[n-1][n-1]);
        return 0;
    } 

    本文来自 Running07 的CSDN 博客 ,全文地址请点击:https://blog.csdn.net/hrn1216/article/details/51534607?utm_source=copy

    展开全文
  • 动态规划最长公共子序列(C语言)

    千次阅读 2018-09-08 12:59:43
    #include &amp;quot;stdafx.h&amp;quot; #include&amp;amp;lt;stdio.h&amp;amp;gt; #define m 7 #define n 6 int c[m + 1][n + 1]; int b[m+1][n+1]; void LCS_LENGTH(char *x,char *y) ... i++)
  • 最长公共子序列 描述#include #include #define MAX_LEN 1001 #define maxValue(a,b) ((a)>(b) ? (a) : (b)) int lcs[MAX_LEN][MAX_LEN] = {0,}; int main() { int N; char strA[MAX_LEN]; char strB[MAX_...
  • 这题是最长公共子序列的变形,要注意的就是,题目要求输出最长上升子序列的字典排序最小值,最麻烦的就是这个,想了半天都没什么思路,我对最长上升子序列的理解不是很透彻。在网上看了别人的题解,都是用一个结构题...
  • 动态规划最长公共子序列(LCS)(附详细填表过程)

    万次阅读 多人点赞 2018-11-20 12:51:34
    动态规划求解最长公共子序列: 分析规律: 做法: 伪代码: 下面演示下c数组的填表过程:(以求ABCB和BDCA的LCS长度为例): 时间复杂度: 代码: 结果示例: 相关概念 子序列形式化定义: 给定一个序列X=...
  • //这样, 公共子序列问题就转化为 公共递增子序列问题 //下面是LIS算法  int stack[maxn]; for (int i = 0; i ; i++) stack[i] = maxn; int ans = 1; for (int i = 0; i ; i++){ int count = lower_bound...
  • 题目描述  给定两个序列X= ...每组输出一行,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输出0。 示例输入 ABCBDAB BDCABA 示例输出 4 提示   #include #include #
  • 主要介绍了Java基于动态规划法实现求最长公共子序列及最长公共子字符串,简单描述了动态规划法的概念、原理,并结合实例形式分析了Java使用动态规划法求最长公共子序列以及最长公共子字符串相关实现技巧,需要的朋友...
  • 动态规划最长公共子序列
  • 动态规划解决最长公共子序列

    千次阅读 2016-03-12 16:37:30
    要求:最长公共子序列,英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。而...
  • 背景:  对于两个给定的序列X ={A,B,C,D,A,B},Y=... 但该动态规划算法着重于分析如何求出一个最长公共子序列,至于求出所有最长公共子序列,或者是多个给定的序列求最长公共子序列还需有待研究! 分析:  动态规划
  • 用Python实现动态规划最长公共子序列和最长公共子串问题!
  • 使用动态规划算法求两个序列的最长公共子序列,需构造一条最长公共子序列。 输入 每组输入包括两行,每行包括一个字符串。 输出 两个字符序列的一条最长公共子序列。(输入已确保最长公共子序列的唯一性) 样例输入 ...
  • 最长公共子序列 对于两个子序列 S1 和 S2,找出它们最长的公共子序列。 定义一个二维数组 dp 用来存储最长公共子序列的长度,其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 ...
  • 题目:给定两个序列X={x1,x2,…xm},Y={y1,y2,…yn},找出X和Y的最长公共子序列。 分析: 1 最长公共子序列概念 实现明确一个点就是,子序列是一个序列中去掉若干元素后得到的序列,也就是说子序列的元素下标是递增...
  • 动态规划解决最长公共子序列

    千次阅读 2020-03-18 10:13:46
    什么是最长公共子序列?  1. 官方定义:最长公共子序列也称作最长公共子串(不要求连续,但要求次序),英文缩写为 LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子...
  • 求解最长公共子序列和最长公共子字符串,运用动态规划算法能很好地解决。  【最长公共子序列】:  一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列 X = { x1,x2,x3,…,xm },则...
  • C#实现-动态规划-最长公共子序列-DPLCS,根据动态规划的思想实现对最长公共子序列的求解。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,673
精华内容 15,469
关键字:

动态规划最长公共子序列