算法设计与分析——最长公共子序列

算法设计与分析——最长公共子序列,第1张

算法设计与分析——最长公共子序列

运用了动态规划原理

若a[i]=b[j],L[i,j]=L[i-1,j-1]+1。

若a[i]!=b[j],L[i,j]=max{L[i,j-1],L[i-1,j]}。

代码如下:

#include
using namespace std;

int main()
{
    int L[100][100];
    char a[5]={'B','D','C','A'};
    char b[5]={'A','B','C','B'};
    for(int i=0;i<=4;i++)
    {
        L[i][0]=0;
    }
    for(int i=0;i<=4;i++)
    {
        L[0][i]=0;
    }
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            if(a[i]==b[j])
            {
                L[i][j]=L[i-1][j-1]+1;
            }
            else
            {
                L[i][j]=max(L[i-1][j],L[i][j-1]);
            }
        }
    }
    cout<					
										


					

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5658406.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存