精华内容
下载资源
问答
  • 1. 最长公共子序列 1.1 问题描述 1.2 思路 利用动态规划。 下一步就要找到状态之间的转换方程。

    1. 最长公共子序列(LCS)

    1.1 问题描述

    在这里插入图片描述

    1.2 思路

    利用动态规划。
    在这里插入图片描述
    下一步就要找到状态之间的转换方程。
    在这里插入图片描述
    因此可以根据这个方程来进行填表,以"helloworld"和“loop”为例:
    在这里插入图片描述

    1.3 Python代码

    def LCS(string1,string2):
        len1 = len(string1)
        len2 = len(string2)
        res = [[0 for i in range(len1+1)] for j in range(len2+1)]
        for i in range(1,len2+1):
            for j in range(1,len1+1):
                if string2[i-1] == string1[j-1]:
                    res[i][j] = res[i-1][j-1]+1
                else:
                    res[i][j] = max(res[i-1][j],res[i][j-1])
        return res,res[-1][-1]
    print(LCS("helloworld","loop"))
    # 输出结果为:
    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
     [0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2],
     [0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3],
     [0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3]], 3
    

    所以"helloworld"和"loop"的最长公共子序列的长度为3。

    1.4 找到具体的子序列

    下面的内容借鉴了博主Running07的博客动态规划 最长公共子序列 过程图解

    如果有两个字符串如下:
    S1 = “123456778”
    S2 = “357486782”
    其最终的动态规划填表结果为:
    在这里插入图片描述
    其中S1和S2的LCS并不是只有1个。
    我们根据递归公式:
    在这里插入图片描述
    构建了上表,
    通过递推公式,可以看出,res[i][j]的值来源于res[i-1][j]或者是res[i-1][j]和res[i][j-1]的较大值(可能相等)。
    我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。
    res[8][9] = 5,且S1[8] != S2[9],所以倒推回去,res[8][9]的值来源于c[8][8]的值(因为res[8][8] > res[7][9])。
    res[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去,res[8][8]的值来源于 res[7][7]。
    以此类推,如果遇到S1[i] != S2[j] ,且res[i-1][j] = res[i][j-1] 这种存在分支的情况,这里都选择一个方向(之后遇到这样的情况,也选择相同的方向,要么都往左,要么都往上)。
    在这里插入图片描述
    可得S1和S2的LCS为{3、5、7、7、8} 这是遇见相等的时候,统一往左走
    S1和S2之间还有一个LCS 这是遇见相等的时候,统一往上走
    在这里插入图片描述
    可得S1和S2的LCS为{3、4、6、7、8}

    2. 最长公共子串

    2.1 问题描述

    在这里插入图片描述

    2.2 思路

    和最长公共子序列一样,使用动态规划的算法。
    下一步就要找到状态之间的转换方程。在这里插入图片描述
    和LCS问题唯一不同的地方在于当A[i] != B[j]时,res[i][j]就直接等于0了,因为子串必须连续,且res[i][j] 表示的是以A[i],B[j]截尾的公共子串的长度。因此可以根据这个方程来进行填表,以"helloworld"和“loop”为例:
    在这里插入图片描述
    这个和LCS问题还有一点不同的就是,需要设置一个res,每一步都更新得到最长公共子串的长度。

    2.3 Python代码

    def LCstring(string1,string2):
        len1 = len(string1)
        len2 = len(string2)
        res = [[0 for i in range(len1+1)] for j in range(len2+1)]
        result = 0
        for i in range(1,len2+1):
            for j in range(1,len1+1):
                if string2[i-1] == string1[j-1]:
                    res[i][j] = res[i-1][j-1]+1
                    result = max(result,res[i][j])  
        return result
    print(LCstring("helloworld","loop"))
    # 输出结果为:2
    
    展开全文
  • 最长公共子序列 例题: 给定两个字符串A和B,同时给定两个串的长度n和m,请返回最长公共子序列的长度。保证两串长度均小于等于300。 测试样例: "1A2C3D4B56",10,"B1D23CA45B6A",12 返回:6解题...

      最长公共子串是在两个String中找出最长的公共部分,子串为连续;

      最长公共子序列是在两个string中找出最长的相同序列,子序列可以不连续;

    最长公共子序列 例题:

    给定两个字符串AB,同时给定两个串的长度nm,请返回最长公共子序列的长度。保证两串长度均小于等于300。

    测试样例:
    "1A2C3D4B56",10,"B1D23CA45B6A",12
    返回:6

    解题思路:用二维数组c[i][j]来表示字符串A中以(i-1)(以i-1这个位置)结尾,字符串B中以(j-1)结尾的子序列长度;
    那么,
    1.
    当A[i-1]==B[j-1]时,c[i][j]=c[i-1][j-1]+1;也就是当前A和B指向的字符相等,那么在位置i-1和位置j-1处的子序列长度在前一个的基础上加1;
    2.当A[i-1]!=B[j-1]时,c[i][j]=max{c[i-1][j],c[i][j-1]},也就是当前A和B指向的字符不相等,那么在位置i和位置j除的子序列长度应该等于c[i-1][j]和
    c[i][j-1]中的较大者。

    最长公共子串 例题:

    给定两个字符串AB,同时给定两串的长度nm

    
    
    测试样例:
    
    
    "1AB2345CD",9,"12345EF",7
    
    
    返回:4

    最大公共子串的思路与上述思路一致,只是当
    A[i-1]!=B[j-1]时,c[i][j]=0。


    最长公共子序列代码示例:
    class LCS {
    public:
        int findLCS(string A, int n, string B, int m) {
            
            int table[n + 1][m + 1];
             
            for(int i = 0;i <= n;++i)table[i][0] = 0;//初始化矩阵的第0列
            for(int i = 0;i <= m;++i)table[0][i] = 0;//初始化矩阵的第0行
             
            for(int i = 1;i <= n;++i){
                for(int j = 1;j < =m;++j){
                    if(A[i-1] == B[j-1])
                        table[i ][j] = table[i - 1][j - 1] + 1;
                    else {
                        table[i][j ] = max(table[i][j - 1],table[i - 1][j]);//等于较大值
                    }
                }
            }
            return table[n][m];
        }
    };
     
    最长公共子串代码示例: 

    class LongestSubstring {
    public:
        int findLongest(string A, int n, string B, int m) {
            
             int c[n+1][m+1];
            int maxlen = 0;
             for(int i = 0;i <= n;++i)  c[i][0] = 0;//初始化矩阵的第0列
            for(int i = 0;i <= m;++i)  c[0][i] = 0;//初始化矩阵的第0行
            //dp
            for(int i = 1; i <=n; ++i){
                for(int j = 1; j <=m; ++j){
                    if(A[i-1] != B[j-1]){
                          c[i][j]=0;
                    }
                    else{
                        //common substring ends with A[i] and B[j]
                              c[i][j] = c[i-1][j-1] + 1;
                          maxlen = maxlen > c[i][j] ? maxlen : c[i][j];
                    }
                }
            }
            return maxlen;
        }
    };
    博主原创博文,未经允许,请勿转载!




    转载于:https://www.cnblogs.com/CassieRyu633/p/4754863.html

    展开全文
  • 1. 最长公共子序列(LCS) 1.1 问题描述 1.2 思路 利用动态规划。 下一步就要找到状态之间的转换方程。 因此可以根据这个方程来进行填表,以"he...

    1. 最长公共子序列(LCS)

    1.1 问题描述

    在这里插入图片描述

    1.2 思路

    利用动态规划。
    在这里插入图片描述
    下一步就要找到状态之间的转换方程。
    在这里插入图片描述
    因此可以根据这个方程来进行填表,以"helloworld"和“loop”为例:
    在这里插入图片描述

    1.4 找到具体的子序列

    如果有两个字符串如下:
    S1 = “123456778”
    S2 = “357486782”
    其最终的动态规划填表结果为:
    在这里插入图片描述

    其中S1和S2的LCS并不是只有1个。
    我们根据递归公式:
    在这里插入图片描述

    构建了上表,
    通过递推公式,可以看出,res[i][j]的值来源于res[i-1][j]或者是res[i-1][j]和res[i][j-1]的较大值(可能相等)。
    我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。
    res[8][9] = 5,且S1[8] != S2[9],所以倒推回去,res[8][9]的值来源于c[8][8]的值(因为res[8][8] > res[7][9])。
    res[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去,res[8][8]的值来源于 res[7][7]。
    以此类推,如果遇到S1[i] != S2[j] ,且res[i-1][j] = res[i][j-1] 这种存在分支的情况,这里都选择一个方向(之后遇到这样的情况,也选择相同的方向,要么都往左,要么都往上)。

    在这里插入图片描述

    可得S1和S2的LCS为{3、5、7、7、8} 这是遇见相等的时候,统一往左走
    S1和S2之间还有一个LCS 这是遇见相等的时候,统一往上走:
    在这里插入图片描述
    可得S1和S2的LCS为{3、4、6、7、8}

    2. 最长公共子串

    2.1 问题描述

    在这里插入图片描述

    2.2 思路

    和最长公共子序列一样,使用动态规划的算法。
    在这里插入图片描述
    下一步就要找到状态之间的转换方程。
    和LCS问题唯一不同的地方在于当A[i] != B[j]时,res[i][j]就直接等于0了,因为子串必须连续,且res[i][j] 表示的是以A[i],B[j]截尾的公共子串的长度。因此可以根据这个方程来进行填表,以"helloworld"和“loop”为例:
    在这里插入图片描述
    这个和LCS问题还有一点不同的就是,需要设置一个res,每一步都更新得到最长公共子串的长度。

    原文链接:https://blog.csdn.net/ggdhs/article/details/90713154

    展开全文
  • 最长公共子序列 问题描述: 题解:以问题中为例: A='helloworld' B='loop' res[i][j]表示:截止到B的第i个字符和截止到A的第j个字符的最长公共子序列 例如:res[2][5]=2表示第2行第5列,也就是lo和hello的...

    最长公共子序列

    问题描述:

    在这里插入图片描述

    题解:以问题中为例:

    A='helloworld'

    B='loop'

    res[i][j]表示:截止到B的第i个字符和截止到A的第j个字符的最长公共子序列

    例如:res[2][5]=2表示第2行第5列,也就是lo和hello的最长公共子序列等于2

      0 h e l l o w o r l d
    0 0 0 0 0 0 0 0 0 0 0 0
    l 0 0 0 1 1 1 1 1 1 1 1
    o 0 0 0 1 1 2 2 2 2 2 2
    o 0 0 0 1 1 2 2 3 3 3 3
    p 0 0 0 1 1 2 2 3 3 3 3

     

     

     

     

     

     

    其推到公式为:

    代码如下:

    def lcs(s, t):
        len1 = len(s)
        len2 = len(t)
        # 初始化一个二维数组,行数为t的大小,列数为s的大小
        res = [[0 for i in range(len1 + 1)] for j in range(len2 + 1)]
        for i in range(1, len2 + 1):
            for j in range(1, len1 + 1):
                if t[i - 1] == s[j - 1]:
                    res[i][j] = 1 + res[i - 1][j - 1]
                else:
                    res[i][j] = max(res[i - 1][j], res[i][j - 1])
        return res[-1][-1]

     

    最长公共子串

    问题描述:

    在这里插入图片描述

    res[i][j]表示:截止到B的第i个字符和截止到A的第j个字符的最长公共子串

    和LCS问题唯一不同的地方在于当A[i] != B[j]时,res[i][j]就直接等于0了,因为子串必须连续,且res[i][j] 表示的是以A[i],B[j]截尾的公共子串的长度。因此可以根据这个方程来进行填表,以"helloworld"和“loop”为例:

      0 h e l l o w o r l d
    0 0 0 0 0 0 0 0 0 0 0 0
    l 0 0 0 1 1 0 0 0 0 1 0
    o 0 0 0 0 0 2 0 1 0 0 0
    o 0 0 0 0 0 1 0 1 0 0 0
    p 0 0 0 0 0 0 0 0 0 0 0

     

     

     

     

     

     

     

    代码中需要一个变量来记录最大公共子串的数值

    代码如下:

    def lcs_string(s, t):
        len1 = len(s)
        len2 = len(t)
        # 初始化一个二维数组,行数为t的大小,列数为s的大小
        res = [[0 for i in range(len1 + 1)] for j in range(len2 + 1)]
        # 声明一个变量,记录最大公共子串的值
        max_len = 0
        for i in range(1, len2 + 1):
            for j in range(1, len1 + 1):
                if t[i - 1] == s[j - 1]:
                    res[i][j] = 1 + res[i - 1][j - 1]
                else:
                    res[i][j] = 0
                max_len = max(max_len, res[i][j])
        return max_len

     

    展开全文
  • 本次博客,直接简述核心动态规划部分,需要先对动态规划以及什么是最长公共子序列有简单了解,可以参考下博客, 最长公共子序列 (LCS) 详解+例题模板(全) ...动态规划最长公共子序列(LCS)(附详细填表过程) ...
  • 有了最长公共子序列的基础,我们就很快能理解什么是最长公共子序列了,看一道例题hud1159: A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a ...
  • 动态规划经典例题——最长公共子序列和最长公共子串(python) 很久之前大概是高中的时候写过这种题目,使用动态规划的方法求解的,现读研究生了,要把过去的拾起来的呢。 1. 最长公共子序列(LCS) 1.1 问题描述 ...
  • 动态规划——最长公共子序列总结

    千次阅读 2015-09-19 10:50:08
    子序列 sub sequence问题,例:最长公共子序列,[LeetCode] Distinct Subsequences(求子序列个数) 子序列和子字符串或者连续子集的不同之处在于,子序列不需要是原...例题1, 最长公共子序列 我们知道最长公共
  • 最长公共子序列,是动态规划的一个典型例题。相比原来的遍历查找,优化明显。 1⃣️、两个序列--Am,Bn,如果Am=Bn,则再去Am-1,Bn-1; 2⃣️、An!=Bm,找其中最大组,即max{{An,Bm-1},{An-1,Bm}}; 3⃣️、两者...
  • 问题:即按两个串的顺序,找出相同的子序列(可跳跃查找)
  • 最长公共子序列,可以拓展到非字符串的结构,如数组等,毕竟其实字符串也可以理解为字符数组 例题: 给两个整数数组A和B,返回两个数组中公共的、长度最长的子数组的长度。 示例0: 输入: A: [1,2,3,2,1] B: [3...
  • 最长公共子序列 一个给定序列的子序列是在该序列中删去若千元素后得到的序列 给定两个序列X和Y ,当另一-序列Z既是X的子序列又是Y的子序列时,称Z是序 列X和Y的公共子序列 最长公共子序列, . X=(A,B,C,B,D,A,B) Y...
  • 给定两个字符串str1和str2,返回两个字符串的最长公共子序列.例如,str1="1A2C3D4B56",str2="B1D23CA45B6A","123456"或者"12C4B6' 动态规划思想: 先用一个比,左边加一个字符...
  • 本期例题:LeetCode 1143. Longest Common Subsequence 最长公共子序列(Medium)给定两个字符串 s 和 t,返回这两个字符串的最长公共子序列的...
  • 动态规划经典例题——最长公共子序列和最长公共子串 求解两个字符串的最长公共子序列(思路nice) 描述 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符...
  • 最长公共子序列 最长公共子串 最长回文子串 回文子串数 最长回文子序列 DP思想 DP和分治策略类似,讲一个问题分成几个子问题,然后地递归的求解这个几个子问题,之后合并子问题的解得到原问题的解。 不同点...
  • 转自:教你彻底学会动态规划——进阶篇 在我的上一篇文章中已经详细讲解了动态规划的原理和如何使用动态... 最长公共子序列(POJ1458)  给出两个字符串,求出这样的一个最长的公共子序列的长度:子序列中的每个...
  • 动态规划最长公共子序列学习。讲解。模板。例题
  • 定义LIS(i):表示以第i个数字为结尾的最长上升子序列的长度LIS(i):表示在[0...i]的范围内,选择数字nums[i]可以获得的最长上升子序列的长度LIS(i) = max(1 + LIS(j)) (i &gt; j)2.例题300. Longest Increasing ...
  • 动态规划案例-最长公共子序列 内含问题理解、表格填写、实例解决以及例题 帮助全方面解决问题 在线博主,及时解答
  • 王道机试 第十二章 动态规划 12.3最长递增子序列(LIS) 12.3 最长递增子序列(LIS) 例题12.3 拦截导弹(北京大学复试上机题) 动态规划解读 设变量 设dp[k]dp[k]dp[k]表示以aka_kak​为结尾的子序列(可以不连续)的...
  • 动态规划算法经典例题不少,最长公共子序列,最大子序列和,0-1背包等等等等,我也考虑一一写道博客上,这次先来讲一讲鄙人刚写完最长公共子序列,新鲜滚热辣 在这个问题里,最优子结构是每一个line1的子字符串与...
  • 例题最长上升子序列(百练2757) 问题描述 一个数的序列ai,当a 1 < a 2 < … < a S 的时候,我们称这个序列是上升的。对于给定的一个序列(a 1 , a 2 , …, a N ),我们可以得到一些上升的子序列(a i1 , a ...
  • 最长公共子序列是一个很经典的动态规划问题,最近正在学习动态规划,所以拿来这里再整理一下。 这个问题在《算法导论》中作为讲动态规划算法的例题出现。   动态规划,众所周知,第一步就是找子问题,也就是把一个...
  • 动态规划最长公共上升子序列(LCIS)算法及优化 例题 题目传送门 描述 给定两个整数序列,写一个程序求它们的最长上升公共子序列。 当以下条件满足的时候,我们将长度为N的序列S1 , S2 , . . . , SN 称为长度...

空空如也

空空如也

1 2 3 4 5 6
收藏数 113
精华内容 45
关键字:

动态规划最长公共子序列例题