在动态规划中查找 LCS 中的比较数

Question

#include<iostream>
#include<string.h>
int count=0;

using namespace std;


int max(int a,int b)
{
    return (a>b)?a:b;
}

int lcs(char *x,char*y ,int m,int n)
{

    int l[m+1][n+1];
    int i,j;

    for( i=0;i<=m;i++)
    {
     for(j=0;j<=n;j++)
        {

        if(i==0 || j==0)
        l[i][j]=0;

        else if(x[i-1]==y[j-1]) 
        l[i][j]=l[i-1][j-1]+1;

        else
        l[i][j] =max(l[i-1][j], l[i][j-1]);

        }
    }


    return l[m][n];


}


int main()
{

    char x[]="AGGTAB";
    char y[]="GXTXAYB";

    int m=strlen(x);
    int n=strlen(y);

    cout<<"The Length Of the Longest Common Subsequence Is  :   "<<lcs(x,y,m,n);
}

以上程序是使用动态规划寻找最大公共子序列的解决方案。我能够计算 LCS 的长度，但我无法推断出找到总数的逻辑。系统将进行比较以找到 lcs 。

我想求总号。比较并使用全局计数变量打印它。有人可以帮帮我吗？

Answer 1

这取决于您将什么算作比较。

我假设，通过比较，你的意思是 "comparing characters in the string"。 IE。 i==0 不算作比较。比较 max 中的值也不算作比较，因为它 而不是 比较字符串中的字符。另外，我没有通过你的程序检查你所做的是否真的正确 - 我只是假设它是并专注于你的实际问题。

也就是说，唯一发生的字符比较是在行中：

else if(x[i-1]==y[j-1])

因此，每次执行此检查时，您都应该增加计数器。一种方法是稍微重组你的分支（而不是 else if 你可以做一个 else{ if{x[i-1]==y[j-1]} }。如果你这样做，那么你可以在 counter 之前增加 counter如果。像这样：

if(){

}else{ 
 counter++;
 if{x[i-1]==y[j-1]} 

 }else{

 }
}

另一种更明确的方法是让一个函数在那里进行检查和递增。类似于：

bool compareChars(char &first, char &second){
 counter++;
 return first == second;
}

然后你只需要做：

else if(compareChars(x[i-1], y[j-1]))

那么很明显，每次比较完成时计数器都会递增。

这个我没有仔细测试过，当然还有其他的方法，还是希望你有个大概的了解。

在动态规划中查找 LCS 中的比较数

Finding Number of Comparison in LCS In dynamic programming

c++

dynamic-programming

lcs

data-structures