动态规划３：最长公共子序列（不连续）

野性酷女 2023-07-09 02:11 11阅读 0赞

//最长公共子序列－－LCS
    
    #include <stdio.h>
    #include "cstring"
    #include "vector"
    #include "algorithm"
    
    using namespace std;
    const int N = 100;
    char A[N], B[N];
    int dp[N][N];//dp[i][j] A的i号位置与B的j号位置之前的LCS长度
    int main() { 
        fgets(A + 1, N, stdin);//从１号位置开始
        fgets(B + 1, N, stdin);
        int lengthA = strlen(A + 1) - 1;
        int lengthB = strlen(B + 1) - 1;
        //边界
        for (int i = 0; i <= lengthA; i++) { 
            dp[i][0] = 0;
        }
        for (int j = 0; j <= lengthB; j++) { 
            dp[0][j] = 0;
        }
        //状态转移方程
    
        for (int i = 1; i <= lengthA; i++) { 
            for (int j = 1; j <= lengthB; j++) { 
    
                if (A[i] == B[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[lengthA][lengthB]);
        return 0;
    }
    
    /* sadstory adminsorry */

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200227114431154.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

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

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

相关阅读

相关 [动态规划][公共子串]最长公共子串、最长公共子序列

1、最长公共子串 LintCode：[https://www.lintcode.com/problem/longest-common-substring/descri...

约定不等于承诺〃/ 2024年04月18日 17:10/ 0 赞/ 71 阅读

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

动态规划：最长公共子序列前言一、动态规划 -------------------- 前言给定两个字符串 text1 和 text2，返回这两个

妖狐艹你老母/ 2024年03月16日 18:40/ 0 赞/ 106 阅读

相关动态规划３：最长公共子序列（不连续）

//最长公共子序列－－LCS include <stdio.h> include "cstring" include "vector"

野性酷女/ 2023年07月09日 02:11/ 0 赞/ 12 阅读

相关动态规划２：最长不下降子序列－－连续序列＋不连续序列

//最长不下降子序列－－连续+不连续 include <cstdio> include "vector" include "algor

梦里梦外;/ 2023年07月09日 02:01/ 0 赞/ 11 阅读

相关动态规划---最大公共子序列（不连续）

比如：“programming” 和 “contest”，可以找到的最长的公共子序列（不连续）是"on",所以最大公共子序列长度（不连续）为 2 1、最开始的思路是递归

蔚落/ 2023年06月25日 02:24/ 0 赞/ 31 阅读

相关动态规划---最大公共子序列（连续）

比如：“abcdkkk” 和 “baabcdadabc”，可以找到的最长的公共子序列（连续）是"abcd",所以最大公共子序列长度（连续）为 4 代码： inc

矫情吗；*/ 2023年06月25日 02:23/ 0 赞/ 21 阅读

相关动态规划---最长上升子序列（不连续）

比如序列（1，7，3，5，9，4，8），它的最长上升序列是（1，3，4，8），所以它的最长上升序列长度为 4，那么给定任意长度的序列，请求出它的最长上升序列长度代码：

刺骨的言语ヽ痛彻心扉/ 2023年06月24日 11:26/ 0 赞/ 26 阅读

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

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

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

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

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

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

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

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

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