精华内容
下载资源
问答
  • LCS动态规划求解方法

    2019-03-01 13:19:38
    LCS动态规划求解方法 利用上图可以看出。 其递推式 类似的oj题目 http://nyoj.top/problem/36 咱们就不拐弯抹角了,如题,需要你做的就是写一个程序,得出最长公共子序列。 t其定义是,一个序列 S ,如果...

    LCS动态规划求解方法

    利用上图可以看出。

    其递推式

     

    类似的oj题目   http://nyoj.top/problem/36

    咱们就不拐弯抹角了,如题,需要你做的就是写一个程序,得出最长公共子序列。
    t其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

    输入描述:

    第一行给出一个整数N(0<N<100)表示待测数据组数
    接下来每组数据两行,分别为待测的两组字符串。每个字符串长度不大于1000.

    输出描述:

    每组测试数据输出一个整数,表示最长公共子序列长度。每组结果占一行。

    AC代码,利用了上述动态规划的思想

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<string>
    using namespace std;
    int dp[1005][1005];
    int main()
    {
        int m;
        cin>>m;
        while(m--){
        string s1,s2;
        cin>>s1>>s2;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=s2.size();i++)
        for(int j=1;j<=s1.size();j++){
            if(s2[i-1]==s1[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[s2.size()][s1.size()]<<endl;
        }
     return 0;
    }
    

     

    展开全文
  • LCS 动态规划

    2019-02-21 13:40:25
    动态规划法 java版 public class LCS { public static String getLCS(String s1, String s2){ System.out.println(&quot;str1:&quot; + s1); System.out.println(&quot;str2:&quot; + s2);...

    动态规划法 java版

    public class LCS {
    
        public static String getLCS(String s1, String s2){
            System.out.println("str1:" + s1);
            System.out.println("str2:" + s2);
            int str1Length = s1.length();
            int str2Length = s2.length();
    
            int[][] matrix = new int[str1Length + 1][str2Length + 1];
            
            for (int i = 1; i < str1Length + 1; i++) {
                for (int j = 1; j < str2Length + 1; j++) {
                    if (s1.charAt(i-1) == s2.charAt(j-1)) {
                        matrix[i][j] = matrix[i - 1][j - 1] + 1;
                    } else {
                        matrix[i][j] = Math.max(matrix[i - 1][j], matrix[i][j - 1]);
                    }
                }
            }
            
            StringBuilder sb = new StringBuilder();
            while((str1Length > 0) && (str2Length > 0)){
                //↖
                if(s1.charAt(str1Length-1) == s2.charAt(str2Length-1)){
                    sb.append(s1.charAt(str1Length-1));
                    str1Length--;
                    str2Length--;
                }else{
                    if(matrix[str1Length][str2Length-1] > matrix[str1Length-1][str2Length]){
                        //←
                        str2Length--;
                    }else{
                        //↑
                        str1Length--;
                    }
                }
            }
            return sb.reverse().toString();
        }
    
        public static void main(String[] args) {
            String s1 = "ABCBDAB";
            String s2 = "BDCABA";
            String lcs = LCS.getLCS(s1, s2);
            System.out.print("LCS:"+ lcs);
        }
       
    }
    

    str1:ABCBDAB
    str2:BDCABA
    LCS:BCBA

    展开全文
  • LCS动态规划算法实现

    2009-12-02 19:23:22
    最长公共子串匹配动态规划算法实现,源代码加注释,可运行啊,这描述限定真死板,还20 字符,吃多了啊
  • 【算法竞赛入门经典】类LCS动态规划;指标函数分解 例题9-7 UVa1625 【算法竞赛入门经典】类LCS动态规划;指标函数分解 例题9-7 UVa1625 例题UVa1625 指标函数 分析 样例实现代码 结果 例题UVa1625 ...

    【算法竞赛入门经典】类LCS动态规划;指标函数分解 例题9-7 UVa1625

    例题UVa1625

    这里写图片描述
    这里写图片描述
    Input
    这里写图片描述

    Output

    这里写图片描述

    Sample Input

    2
    AAABBCY
    ABBBCDEEY
    GBBY
    YRRGB

    Sample Output

    10
    12

    指标函数

    指标函数和最优值函数
    指标函数即用来衡量所实现过程优劣的数量指标,它定义在全过程和所有后部子过程上确定的数量函数,用 Vk,n 表示,即 Vk,n = Vk,n(sk, uk, sk+1, uk+1, … , sn+1) , k = 1, 2, …, n。该指标函数应该具有可分离性,并满足递推关系,即Vk,n可以表示为sk,uk,Vk+1,n的函数。常见的指标函数有(1)过程和它的任一子过程的指标是它所包含的各个阶段的指标的和;(2)过程和它的任一子过程的指标是它所包含的各个阶段的指标的乘积。
    最优值函数是指标函数的最优值,记为fk(sk),表示从第k阶段的状态开始到第n阶段的终止状态的过程,采取最优策略所得到的指标函数值(一般是最大/最小值),即:
    这里写图片描述
    不同的问题中指标函数的含义不同,可能是距离、利润、成本、产量或资源消耗等等。

    分析

    利用dp[i]表示第一串字符放置i个且第二串字符放置j个之后的当前消耗。
    其实状态转移方程比较好写。

    dp[i][j]=min(dp[i-1][j]+c(i),dp[i][j-1]+c(j));

    c(i)或是c(j)的含义就是当前放置一个字符之后多出的消耗。
    但是这个c()函数算起来是非常的不便利,如果每次放置都去重新更新元素的距离跨度是难以接受的。
    因此我们尝试简化这个c()函数。
    事实上,每次移动一个元素的时候,如果有元素出现了第一个且没有出现最后一个,即该元素没有结束,那么该元素的耗费势必增加。进一步的,我们不需要关心具体是哪个颜色,只要知道有多少个颜色没有结束就可以了。这样每次更新的c()函数可以理解为,没有结束的颜色引起的耗费增加,每一个元素引起的耗费+1
    这样用c[i][j]数组进行统计,当插入某个元素时候的耗费。c[i][j]的计算应该也算一个dp的过程,实际上两个dp同时进行了。只不过c[i][j]的更新和某个元素有没有结束有关,方便起见可以提前统计每个颜色的开始结束位置。
    除此之外,这里的memset没有必要使用,因为递推从前到后且dp[0][0]不会变,因此memset反而浪费了时间。

    样例实现代码

    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #define maxn 5000+5
    #define INF 1000000
    using namespace std;
    int dp[maxn][maxn],c[maxn][maxn],stp1[26],stp2[26],enp1[26],enp2[26];
    char p1[maxn],p2[maxn];
    int main(){
        int T;
        cin>>T;
        while(T--){
        //  memset(dp,0,sizeof(dp));
        //  memset(c,0,sizeof(c));
        //这里的memset没有必要,花费大量时间且无用 
            scanf("%s%s",p1+1,p2+1);
            int n1=strlen(p1+1),n2=strlen(p2+1);
            for(int i=1;i<=n1;i++)
                p1[i]-='A';
            for(int j=1;j<=n2;j++)
                p2[j]-='A';
            for(int i=0;i<26;i++){
                stp1[i]=stp2[i]=maxn;
                enp1[i]=enp2[i]=0;
            }
            for(int i=1;i<=n1;i++){
                stp1[p1[i]]=min(stp1[p1[i]],i);
                enp1[p1[i]]=i;
            }
            for(int i=1;i<=n2;i++){
                stp2[p2[i]]=min(stp2[p2[i]],i);
                enp2[p2[i]]=i;
            }
            for(int i=0;i<=n1;i++){
                for(int j=0;j<=n2;j++){
                    if(i==0&&j==0)
                        continue;
                    int p1v=INF,p2v=INF;
                    if(i)
                        p1v=dp[i-1][j]+c[i-1][j];
                    if(j)
                        p2v=dp[i][j-1]+c[i][j-1];
                    dp[i][j]=min(p1v,p2v);
                    if(dp[i][j]==p1v){
                        c[i][j]=c[i-1][j];
                        if(stp1[p1[i]]==i&&stp2[p1[i]]>j)
                            c[i][j]++;
                        if(enp1[p1[i]]==i&&enp2[p1[i]]<=j)
                            c[i][j]--;
                    }
                    else{
                        c[i][j]=c[i][j-1];
                        if(stp2[p2[j]]==j&&stp1[p2[j]]>i)
                            c[i][j]++;
                        if(enp2[p2[j]]==j&&enp1[p2[j]]<=i)
                            c[i][j]--;
                    }
                }
            }
            cout<<dp[n1][n2]<<endl;
        }
        return 0;
    } 
    

    结果

    这里写图片描述

    展开全文
  • 最长公共子串要求在原字符串中是连续的,而子序列只需要保持相对顺序一致,并不要求连续。... def lcs(self,s1,s2): max_len=0 max_index=0 m=len(s1) n=len(s2) dp=[[0]*(n+1) for i in range(m+1)]

    最长公共子串要求在原字符串中是连续的,而子序列只需要保持相对顺序一致,并不要求连续。

    下面我分享一下dp的方法,时间复杂度O(mn),空间复杂度O(mn)

    class Solution:
        def lcs(self,s1,s2):
            max_len=0
            max_index=0
            
            m=len(s1)
            n=len(s2)
            dp=[[0]*(n+1) for i in range(m+1)]
            for i in range(m+1):
                for j in range(n+1):
                    if(i==0 or j==0):
                        continue
                    elif(s1[i-1]==s2[j-1]):
                        dp[i][j]=dp[i-1][j-1]+1
                        if(dp[i][j]>max_len):
                            max_len=dp[i][j]
                            max_index=i-max_len
            return max_len,max_index,s1[max_index:max_index+max_len]
                    
    
    if __name__=="__main__":
        solution=Solution()
        s1='acbac'
        s2='acaccbabb'
        max_len,max_index,seq=solution.lcs(s1,s2)
        print(max_len,max_index,seq)

    有兴趣的人可以帮我找找bug哈,我感觉没啥问题,如果能帮我找到bug,那就万分感谢了,哈哈哈

    参考文献

    [1].算法设计 - LCS 最长公共子序列&&最长公共子串 &&LIS 最长递增子序列. https://blog.csdn.net/sushauai/article/details/50118073

    [2].最长公共子串和最长公共子序列. https://www.cnblogs.com/fengziwei/p/7827959.html

    展开全文
  • 问题题目:[最长公共子序列]思路[参考这一篇]代码class LCS { public: int findLCS(string A, int n, string B, int m) { // write code here if( !n || !m ) return 0; std::vector< std::vector<i
  • set<node> slcs;//默认是小根堆 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int index = 1; int len1 = text1.length(); int len2 = text2.length(); dp = vector...
  • //求s1与s2的LCS L为S长度 那么 c[Ls1][Ls2]就是s1与s2的最大LCS长度 if(c[s1.length()][s2.length()]>maxlength) { ans = i; maxlength = c[s1.length()][s2.length()]; } } s1 = s....
  • #include #include int max( int a, int b ) { return a > b ? a : b; } int d[1001][1001]; char s1[2000]; char s2[2000]; int main() { int la, lb, N; scanf( "%d", &N );... memset( d, 0
  • 算是复习一下LCS的DP求法吧,毕竟学了这么久了看题先:description: 基因匹配(match) 卡卡昨天晚上做梦梦见他和可可来到了另外一个星球,这个星球上生物的DNA序列由无数种碱基排列而成(地球上只有4种),而更...
  • lcs = LCS(); cout "最长公共子序列长度为:" << lcs ; cout "最长公共子序列为:" ; Print(s1_len - 1 , s2_len - 1 ); cout "\n相似度为:" (lcs * 2 * 100 ) / (s1_len + s2_len) "%\n" ; ...
  • 给你两个字符串,求LCS的长度,一个不超过100W,一个不超过1000 思路: 正常的LCS的dp肯定不能进行,这样会超时。 令dp[i][j]表示当前枚举的LCS的长度为第i位,字符为第二个字符串的的第j 个字符。dp[i][j] 为第一个...
  • 给出两个字符串A B,求A与B的最长公共子序列(子序列不要求是连续的)。 比如两个串为: abcicba abdkscab ...ab是两个串的子序列,abc也是,abca也是,其中abca是这两个字符串最长的子序列。...
  • http://poj.org/problem?id=2250最长公共子序列LCS 动态规划DP CompromiseTime Limit: 1000MS Memory Limit: 65536K Special JudgeDescriptionIn a few months the European Currency Union will become a ...
  • Problem Description It is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T....
  • 动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS
  • LIS & LCS动态规划)

    2021-01-20 08:39:40
    问题描述 东东有两个序列A和B。...这个题是基本的动态规划问题,LIS是最长上升子序列,LCS是最长公共子序列。 求解LIS就是设dp[i]为以当前元素结尾的最长上升序列,那么dp[i]=max(dp[j]∣j<i&&a
  • LCS问题具有最优子结构 令 X=<x1,x2,...,xm>X=<x1,x2,...,xm> 和 Y=<y1,y2,...,yn>Y=<y1,y2,...,yn> 为两个序列,Z=<z1,z2,z3,...,zk>Z=<z1,z2,z3,...,zk>为XX和YY的任意LCS。...
  • 动态规划——LCS

    2016-09-06 21:12:35
    动态规划分为四个步骤: 1.判断问题是否具有最优子结构 这里以LCS为例,X={x1,x2,…,xi};Y={y1,y2,…,yj}。最长公共子序列Z={z1,z2,…,zk}; ①如果xi=yj,那么zk=xi=yj,且Zk-1是序列Xi-1和Yj-1的LCS; ②如果...
  • 动态规划LCS

    2018-07-31 18:13:51
    LCS是Longest Common Subsequence的缩写,即最长公共子序列。一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则为最长公共子序列。  两个序列X和Y的公共子序列中,长度最长的那个,定义为X...
  • 动态规划解最长公共子序列(LCS)(附详细填表过程)

    万次阅读 多人点赞 2018-11-20 12:51:34
    动态规划求解最长公共子序列: 分析规律: 做法: 伪代码: 下面演示下c数组的填表过程:(以求ABCB和BDCA的LCS长度为例): 时间复杂度: 代码: 结果示例: 相关概念 子序列形式化定义: 给定一个序列X=...
  • 最长公共子序列(LCS动态规划解题笔记 参考: 动态规划解最长公共子序列问题 动态规划 最长公共子序列 过程图解 动态规划基础篇之最长公共子序列问题 题意 子序列和最子串的区别在于子串需要连续,但子序列...
  • 动态规划:LIS&LCS

    2020-04-26 16:49:21
    Vjudge:动态规划经典问题LCS LIS
  • LCS-动态规划算法详解

    2020-06-22 23:36:34
    LCS 思想讲解: #include<iostream> #include<string.h> using namespace std; /** * @param {type} string X I am argument string X. * @param {type} string Y I am argument string Y. * @...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,693
精华内容 4,277
关键字:

lcs动态规划