如何打印最长的公共子序列？

Question

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

我的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);，即你include元素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语句拆分为两个if。

现在存储为每对选择的三个选择中的哪个(x,y)，重构最佳解决方案应该很简单。