DP+（POJ1458) 最长公共子序列

清疚 2022-08-18 00:40 158阅读 0赞

题意：

给出两个字符串，求出这样的一个最长的公共子序列的长度：

子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。

解析：看代码最后部分

//最长公共子序列（POJ1458)
    
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <cmath>
    using namespace std;
    
    int const maxn = 1005;
    
    int dp[maxn][maxn];
    string s1,s2;
    
    int main()
    {
        //scanf("%d",&t);
        while(cin>>s1>>s2)
        {
    
            int n1=s1.size();
            int n2=s2.size();
            for(int i = 0 ; i <= n1 ; i++)
            {
                dp[i][0]=0;
            }
            for(int i = 0 ; i <= n2 ; i++)
            {
                dp[0][i]=0;
            }
            for(int i = 1 ; i <= n1 ; i++)
            {
                for(int j = 1 ; j <= n2 ; j++)
                {
                    if(s1[i-1]==s2[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[i][j];
                }
            }
            printf("%d\n",dp[n1][n2]);
        }
        return 0;
    }
    
    /*
    Auther:LIUYAN
    2015.11.30
    
    dp[i][j]s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串
    的最长公共子序列的长度(i,j从0开始算）,求dp[n1][n2]
    dp[0][i]=0,dp[i][0]=0;
    
    if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;
    else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
    
    
    100
    abcfbc abfcab
    programming contest
    abcd mnp
    */

发表评论取消回复

表情：

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

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

相关阅读

相关最长公共子序列

最长公共子序列 1、参考资料 https://leetcode-cn.com/problems/longest-common-subsequence/ 2、题目

阳光穿透心脏的1/2处/ 2022年12月09日 04:57/ 0 赞/ 242 阅读

相关最长公共子序列

include <iostream> include <assert.h> include <string> using namesp

男娘i/ 2022年09月30日 10:00/ 0 赞/ 221 阅读

相关最长公共子序列

最长公共子序列时间限制：3000 ms | 内存限制：65535 KB 难度：3 描述咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列

骑猪看日落/ 2022年09月30日 06:28/ 0 赞/ 224 阅读

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

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

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

相关 dpPOJ 2027 LCIS（最长上升公共子序列）

题意和解析见代码最后部分 include<iostream> include <cstdio> include <cstring>

我不是女神ヾ/ 2022年08月18日 00:48/ 0 赞/ 158 阅读

相关 DP+（POJ1458) 最长公共子序列

题意：给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。解析：看代码最后部

清疚/ 2022年08月18日 00:40/ 0 赞/ 159 阅读

相关 poj1458-Common Subsequence（最长公共子序列，LCS）

Common Subsequence <table style="text-align:center"> <tbody> <tr> <td><strong>

墨蓝/ 2022年08月04日 12:36/ 0 赞/ 75 阅读

相关最长公共子序列

最长公共子序列问题，具有最优子结构性质设序列Xm=\{x1,x2,…,xm\}和Yn=\{y1,y2,…,yn\}的最长公共子序列为Zk=\{z1

港控/mmm°/ 2022年04月23日 07:04/ 0 赞/ 276 阅读

相关最长公共子序列

找出两个字符串的最长公共子序列。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

r囧r小猫/ 2021年11月09日 17:10/ 0 赞/ 414 阅读

相关最长公共子序列

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

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