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

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

最长公共子序列

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

动态规划：

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

问题描述： 设有字符串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]);}

结果

时间复杂度：

由于只需要填一个m行n列的二维数组，其中m代表第一个字符串长度，n代表第二个字符串长度，所以时间复杂度为O（m*n）。

“C++动态规划怎么实现查找最长公共子序列”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注本站网站，小编将为大家输出更多高质量的实用文章！