C语言动态规划&背包最长公共子序列问题

谁借莪１个温暖的怀抱￠ 2022-06-01 08:59 168阅读 0赞

### 最长公共子序列问题 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

给定两个序列X=

#### Input ####

输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。

#### Output ####

每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。

#### Example Input ####

ABCBDAB
    BDCABA

#### Example Output ####

4

#include<stdio.h>
    #define  N 500
    #include <string.h>
    int main()
    {
        int i,j,m,n,c[N][N];
        char X[N],Y[N];
        while(gets(X)&&gets(Y))
        {
            m=strlen(X);
            n=strlen(Y);
            for ( i=0; i<=m; i++ ) 	c[i][0]=0;
            for ( j=0; j<=n; j++ ) 	c[0][j]=0;
            for ( i=1; i<=m; i++ )
                for ( j=1; j<=n; j++ )
                {
                    if (X[i-1]==Y[j-1])
                        c[i][j]=c[i-1][j-1]+1;
                    else
                        if  ( c[i-1][j] > c[i][j-1] )    c[i][j] = c[i-1][j];
                    else   c[i][j] = c[i][j-1];
                }
            printf("%d\n",c[m][n]);
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2381/pid/2080.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2381/pid/2080.html

发表评论取消回复

表情：

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

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

相关阅读

相关动态规划探秘：C语言实现背包问题与最长公共子序列

动态规划探秘：C语言实现背包问题与最长公共子序列动态规划是计算机科学中一个强大且广泛应用的算法思想，它在解决一类具有重叠子问题和最优子结构性质的问题时表现出色。本篇博客

亦凉/ 2023年10月14日 22:01/ 0 赞/ 7 阅读

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

【题⺫】给定两个字符串 str1 和 str2，返回两个字符串的最长公共子序列。【举例】 str1 =“1 A2 C 3 D 4 B5 6 ”， str2

本是古典何须时尚/ 2022年08月18日 02:19/ 0 赞/ 187 阅读

相关动态规划—最长公共子序列问题

最长公共子序列问题 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 给定两个序列X=

ゝ一纸荒年。/ 2022年07月11日 04:27/ 0 赞/ 237 阅读

相关最长公共子序列问题——动态规划

Think: 1递推关系： a\[i\]\[j\] = 0//i == 0 || j == 0 a\[i\]\[j\] = a\[i-1\]\[j-1\] + 1/

绝地灬酷狼/ 2022年06月17日 03:46/ 0 赞/ 220 阅读

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

【例9.9】最长公共子序列时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】一个给定序列的子序列是在该序列中删去若干元素后得到

╰半橙微兮°/ 2022年06月08日 10:06/ 0 赞/ 220 阅读

相关 C语言动态规划&背包最长公共子序列问题

最长公共子序列问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Proble

谁借莪１个温暖的怀抱￠/ 2022年06月01日 08:59/ 0 赞/ 169 阅读

相关 C语言动态规划&背包最长上升子序列

最长上升子序列 Time Limit: 3000MS Memory Limit: 65536KB [Submit][] [Statistic][] Problem

蔚落/ 2022年06月01日 08:40/ 0 赞/ 223 阅读

相关动态规划-最长公共子序列

一，问题描述给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB 则这

痛定思痛。/ 2022年05月11日 11:50/ 0 赞/ 260 阅读

相关动态规划---求最长公共子序列和最长公共子串（C语言）

参考：[https://blog.csdn.net/someone\_and\_anyone/article/details/81044153][https_blog.csdn

阳光穿透心脏的1/2处/ 2022年02月20日 07:08/ 0 赞/ 231 阅读

相关动态规划问题 —— 最长公共子序列

题目描述链接：[https://www.nowcoder.com/questionTerminal/c996bbb77dd447d681ec6907ccfb488a][

淩亂°似流年/ 2022年02月19日 05:43/ 0 赞/ 243 阅读