位置：首页-资讯-后端开发

C++动态规划怎么实现查找最长公共子序列

2023-07-02 14:24

短信预约 -IT技能 免费直播动态提醒

本篇内容介绍了“C++动态规划怎么实现查找最长公共子序列”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

最长公共子序列

最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。一个数列，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。

动态规划：

采用二维数组flag来记录下标i和j的走向。数字"1"表示，斜向下；数字"2"表示，水平向右；数字"3"表示，竖直向下

C++动态规划怎么实现查找最长公共子序列

问题描述：设有字符串a[0…n]，b[0…m]，下面就是递推公式。字符串a对应的是二维数组num的行，字符串b对应的是二维数组num的列。

代码实现

#include<stdio.h>#include<string.h>char a[500],b[500];char num[501][501]; ///记录中间结果的数组char flag[501][501];    ///标记数组，用于标识下标的走向，构造出公共子序列void LCS(); ///动态规划求解void getLCS();    ///采用倒推方式求最长公共子序列int main(){    int i;    strcpy(a,"ABCBDAB");    strcpy(b,"BDCABA");    memset(num,0,sizeof(num));    memset(flag,0,sizeof(flag));    LCS();    printf("%d\n",num[strlen(a)][strlen(b)]);    getLCS();    return 0;}void LCS(){    int i,j;    for(i=1;i<=strlen(a);i++)    {        for(j=1;j<=strlen(b);j++)        {            if(a[i-1]==b[j-1])   ///注意这里的下标是i-1与j-1            {                num[i][j]=num[i-1][j-1]+1;                flag[i][j]=1;  ///斜向下标记            }            else if(num[i][j-1]>num[i-1][j])            {                num[i][j]=num[i][j-1];                flag[i][j]=2;  ///向右标记            }            else            {                num[i][j]=num[i-1][j];                flag[i][j]=3;  ///向下标记            }        }    }}void getLCS(){    char res[500];    int i=strlen(a);    int j=strlen(b);    int k=0;    ///用于保存结果的数组标志位    while(i>0 && j>0)    {        if(flag[i][j]==1)   ///如果是斜向下标记        {            res[k]=a[i-1];            k++;            i--;            j--;        }        else if(flag[i][j]==2)  ///如果是斜向右标记            j--;        else if(flag[i][j]==3)  ///如果是斜向下标记            i--;    }    for(i=k-1;i>=0;i--)        printf("%c",res[i]);}