代码之家 › 专栏 › 技术社区 › Paras Gupta

我可以使用动态规划的自顶向下方法打印LCS吗?

dynamic-programming

Paras Gupta · 技术社区 · 7 年前

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

1 回复 | 直到 7 年前

j3r3mias 6 年前

你需要使用你的 memo 当你比较两个字符串时。如果它们相等,你在对角线处跳跃,如果它们不同,你可以寻找向上和向左跳转到主对角线处。

我有一个类似于你的代码。唯一的区别是,我从字符串的末尾看到开头:

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")) .

所以,我的 备忘录 (考虑到您的解决方案,情况相反)将生成下表:

+-------------------------+
|         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  -  -   |
+-------------------------+

算法位置跳到左上对角线(位置 P ). 在接下来的步骤中,算法将继续运行,直到与字符匹配为止 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