我可以使用自上而下的动态规划方法打印 LCS 吗？

debugcn 发表于 Dev

帕拉斯·古普塔

我知道有一个使用自下而上的方法的解决方案。但我无法在任何地方使用自上而下的方法找到任何解决方案。这是我用于查找 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;
}

j3r3mias

你需要使用你的memowhile 比较两个字符串来做到这一点。如果它们相等，则在对角线处跳跃，如果不同，则可以向上和向左寻找跳到主要的对角线。

我有一个和你类似的代码。唯一的区别是我从字符串的结尾看向开头：

int lcs(char *x, char *y, int px, int py)
{
    int ans;
    int m1, m2;
    if (memo[px][py] > -1) {
         return memo[px][py];
    }
    if ((px == 0) || (py == 0)) {
        ans = 0;
    } else if (x[px - 1] == y[py - 1]) {
        ans = lcs(x, y, px - 1, py - 1) + 1;
    } else {
        m1 = lcs(x, y, px    , py - 1);
        m2 = lcs(x, y, px - 1, py    );
        //max (m1, m2)
        if (m1 > m2) {
            ans = m1;
        } else {
            ans = m2;
        }
    }
    memo[px][py] = ans;
    return ans;
}

要打电话lcs，你可以做lcs("marvin", "panic", strlen("marvin"), strlen("panic"))。

因此，我的memo（考虑到您的解决方案而倒置）将生成下表：

+-------------------------+
|         p  a  n  i  c   |
+-------------------------+
|   | -1  0  0  0  0  0   |
| m |  0  0  0  0  0  0   |
| a |  0  0  1  1  1  1   |
| r |  0  0  1  1  1  1   |
| v |  0  0  1  1  1  1   |
| i |  0  0  1 -1  2  2   |
| n | -1 -1 -1  2  2  2   |
+-------------------------+

为了恢复子字符串，我们从两个字符串 ([6, 5]) 的末尾开始寻找相等的字符。如果它们不相等，我们会在向上的位置查看表格的内容。如果这个位置比左边大，我们往上走，否则我们往左边走。这表示为以下代码：

px = strlen("marvin");
py = strlen("panic");
pos = 0;
while ((px != 0) && (py != 0)) {
    if (x[px - 1] == y[py - 1]) {
        res[pos++] = x[px - 1];
        px--;
        py--;
    } else if (memo[px - 1][py] > memo[px][py -1]) {
        px--;
    } else {
        py--;
    }
}
res[pos] = '\0';
printf("%s\n", strrev(res));

这段代码将从最后开始，向左移动直到找到字符n（位置F）。

+-------------------------+
|         p  a  n  i  c   |
+-------------------------+
|   | -1  0  0  0  0  0   |
| m |  0  0  0  0  0  0   |
| a |  0  0  1  1  1  1   |
| r |  0  0  1  1  1  1   |
| v |  0  0  1  1  1  1   |
| i |  0  0  P -1  2  2   |
| n | -1 -1 -1  F  -  -   |
+-------------------------+

当它找到字符时n，算法位置会在上左对角线（位置P）处跳转。在接下来的步骤中，算法会上升，直到与 char 匹配a。

+-------------------------+
|         p  a  n  i  c   |
+-------------------------+
|   | -1  0  0  0  0  0   |
| m |  0  P  0  0  0  0   |
| a |  0  0  F  1  1  1   |
| r |  0  0  |  1  1  1   |
| v |  0  0  |  1  1  1   |
| i |  0  0  | -1  2  2   |
| n | -1 -1 -1  \  -  -   |
+-------------------------+

最后一步它将向左移动，直到px到达零的位置并且算法停止。

+-------------------------+
|         p  a  n  i  c   |
+-------------------------+
|   | -1  0  0  0  0  0   |
| m |  -  -  0  0  0  0   |
| a |  0  0  \  1  1  1   |
| r |  0  0  |  1  1  1   |
| v |  0  0  |  1  1  1   |
| i |  0  0  | -1  2  2   |
| n | -1 -1 -1  \  -  -   |
+-------------------------+

Obs：结果将会na并且需要被恢复（an）。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。