我可以使用自顶向下的动态编程方法打印LCS吗？(Can I print the LCS using top down approach of dynamic programming?)

 我知道有一种使用自下而上方法的解决方案。 但我无法在任何地方使用自顶向下的方法找到任何解决方案。 以下是我用于查找LCS中字符数的代码： 
 
#include <bits/stdc++.h>

using namespace std;

int memo[100][100];


int LCS(string a,string b,int x,int y){
    if(x==a.size() || y==b.size())
    { memo[x][y]=0; 

        return 0;

     }

    if(a[x]==b[y])
    {   


        if(memo[x][y]==-1){
            memo[x][y]=LCS(a,b,x+1,y+1);
        }

        return 1+ memo[x][y];

    }
    else
    {       
        if(memo[x][y]==-1)
            memo[x][y]=max(LCS(a,b,x+1,y),LCS(a,b,x,y+1));

           return memo[x][y];
    }
}

int main(int argc, char const *argv[])
{
    string a,b;
    cin>>a>>b;
    memset(memo,-1,sizeof(memo));
    cout<<LCS(a,b,0,0)<<endl;
    return 0;
}

I know there is a solution using the bottom-up approach. But I couldn't find any solution using top-down approach anywhere. Here is the code I'm using for finding the number of characters in LCS:
 
#include <bits/stdc++.h>

using namespace std;

int memo[100][100];


int LCS(string a,string b,int x,int y){
    if(x==a.size() || y==b.size())
    { memo[x][y]=0; 

        return 0;

     }

    if(a[x]==b[y])
    {   


        if(memo[x][y]==-1){
            memo[x][y]=LCS(a,b,x+1,y+1);
        }

        return 1+ memo[x][y];

    }
    else
    {       
        if(memo[x][y]==-1)
            memo[x][y]=max(LCS(a,b,x+1,y),LCS(a,b,x,y+1));

           return memo[x][y];
    }
}

int main(int argc, char const *argv[])
{
    string a,b;
    cin>>a>>b;
    memset(memo,-1,sizeof(memo));
    cout<<LCS(a,b,0,0)<<endl;
    return 0;
}

原文：https://stackoverflow.com/questions/47013760