hdu1159 最长公共子序列

Love The Way You Lie 2022-07-31 05:31 192阅读 0赞

简单题，要求两个字符串的最长公共子序列。dp\[i\]\[j\]表示的是第一个字符串的前i个子串和第二个字符串的前j个子串的最长公共子序列 。

//最长公共子序列
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    const int maxn = 1005;
    int dp[maxn][maxn];
    //dp[i][j]表示的是第一个字符串的前i个子串和第二个字符串的前j个子串的最长公共子序列
    char str1[maxn],str2[maxn];
    
    int main()
    {
        while(scanf("%s%s",str1+1,str2+1)!=EOF)
        {
            int n1 = strlen(str1+1);
            int n2 = strlen(str2+1);
            for(int i = 1 ; i <= n1 ; i++)
            {
                dp[i][0] = 0 ;
            }
            for(int i = 1 ; i <= n2 ; i++)
            {
                dp[0][i] = 0 ;
            }
            for(int i = 1 ; i <= n1 ; i++)
            {
                for(int j = 1 ; j <= n2 ; j++)
                {
                    if(str1[i]==str2[j])dp[i][j] = dp[i-1][j-1] + 1 ;
                    else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
            printf("%d\n",dp[n1][n2]);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，192人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1159 Common Subsequence（最长公共子序列）dp

Common Subsequence Problem Description A subsequence of a given sequence is the

男娘i/ 2024年02月17日 19:25/ 0 赞/ 41 阅读

相关 HDU 1159(最长公共子序列)

题意：给出两个字符串，求最长公共子序列。 include <cstdio> include <cstring> include <vecto

港控/mmm°/ 2022年09月20日 11:22/ 0 赞/ 16 阅读

相关 hdu1159Common Subsequence（动态规划之最长公共子序列）

Common Subsequence Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/3276

浅浅的花香味﹌/ 2022年08月21日 10:47/ 0 赞/ 8 阅读

相关最长公共子序列空间优化最长公共子序列

import java.util.Scanner; / HDU 1159 @author ashzheng 201

ゞ浴缸里的玫瑰/ 2022年08月21日 05:46/ 0 赞/ 266 阅读

相关 hdu1159 最长公共子序列

简单题，要求两个字符串的最长公共子序列。dp\[i\]\[j\]表示的是第一个字符串的前i个子串和第二个字符串的前j个子串的最长公共子序列。 //最长公共

Love The Way You Lie/ 2022年07月31日 05:31/ 0 赞/ 193 阅读

相关 HDU 1159-Common Subsequence(LCS 最长公共子序列)

Common Subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K

末蓝、/ 2022年07月24日 08:28/ 0 赞/ 169 阅读

相关 HDU 1159(动态规划-最长公共子序列)

问题描述: A subsequence of a given sequence is the given sequence with some elements (possi

缺乏、安全感/ 2022年06月06日 06:59/ 0 赞/ 161 阅读

相关 HDU 1159 Common Subsequence （最长公共子序列）

　　文章作者：ktyanny 文章来源：[ktyanny][] 转载请注明，谢谢合作。　　　　 ktyanny本打算复习考试周研究一下动态规划，今天早上起得很晚，爬起来

蔚落/ 2021年12月20日 14:11/ 0 赞/ 240 阅读

相关最长公共子序列

最长公共子序列设X=<x1,x2,x3,x4…,xm>，Y=<y1,y2,y3,y4…,yn>为两个序列，Z=<z1,z2,z3,z4…,zk>是他们的任意公共子序列

迈不过友情╰/ 2021年10月19日 05:48/ 0 赞/ 373 阅读

相关 HDU 1159.Common Subsequence（DP 最长公共子序列）超详细题解

目录 1.题目 2.题意 3.思路 4.代码 1.题目 A

缺乏、安全感/ 2021年07月24日 22:42/ 0 赞/ 360 阅读