c++ - 如何打印最长公共(public)子序列？

Question

我正在学习 lcs 并实现它..但是找不到打印最长公共(public)子序列的方法..如何打印它？？

我的 lcs 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int dp[1005][1005];
char a[1005],b[1005];

int lcs(int x,int y)
{
   if(x==strlen(a)||y==strlen(b))
     return 0;
   if(dp[x][y]!=-1)
      return dp[x][y];
   else if(a[x]==b[y])
      dp[x][y]=1+lcs(x+1,y+1);
   else
     dp[x][y]=max(lcs(x+1,y),lcs(x,y+1));
   return dp[x][y];
}
int main()
{
   while(gets(a)&&gets(b))
   {
      memset(dp,-1,sizeof(dp));
      int ret=lcs(0,0);
      printf("%d\n",ret);
   }
}

Answer 1

当您想恢复最佳解决方案时使用 dp 的典型方法 - 添加第二个数组，其大小与您内存的数组完全相同，并将您决定采用的“路径”存储在其中。在这种情况下，您决定采用的“路径”是指通向最佳解决方案的分支。

看看您实现 LCS 的方式，您有三个选项 lcs(x, y) :

• 当您执行 1+lcs(x+1,y+1); 时，它会达到最佳结果即你包括元素 x来自 a和元素 y来自 b.
• 您没有使用元素 x来自 a .如果你得到 dp[x][y]=max(lcs(x+1,y),lcs(x,y+1)); 就会发生这种情况事实上lcs(x+1, y)是两个值中较大的一个。
• 您没有使用元素 y来自 b .如果你得到 dp[x][y]=max(lcs(x+1,y),lcs(x,y+1)); 就会发生这种情况事实上lcs(x, y+1)是两个值中较大的一个。

两个最低的项目符号意味着您必须将此 max 语句拆分为两个 ifs。

现在存储您为每对选择的三个选项中的哪一个 (x,y)重建最佳解决方案应该非常简单。