使用记忆的最长公共子序列

Question

这个程序是使用记忆的最长公共子序列。但它为以下示例提供了答案 0。在添加记忆之前，它给出了正确答案 2.

我想我在添加记忆时做错了。谁能帮我解决这段代码有什么问题吗？

#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
 char a[100]="bd",b[100]="abcd";
 int lcs1[100][100];

 int lcs(int i,int j){
     int temp;
     if(lcs1[i][j]!=-1)

     if(a[i]=='[=10=]'||b[i]=='[=10=]'){
        return 0;
     }
     if(lcs1[i][j]!=-1)
        return lcs1[i][j];
     else if (a[i]==b[j])
        temp = 1+lcs(i+1,j+1);
     else
        temp = max(lcs(i+1,j),lcs(i,j+1));
     lcs1[i][j] = temp;
     return temp;

 }
 int main(){

     int temp = lcs(0,0);
     memset(lcs1,-1,sizeof(lcs1));
     printf("%d",temp);

 }

Answer 1

2 个问题：

您在调用 lcs()
您的 lcs()

if

这里是更正后的代码：

#include<cstring>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
 char a[100]="bd",b[100]="abcd";
 int lcs1[100][100];

 int lcs(int i,int j){
     int temp;
     //if(lcs1[i][j]!=-1)       // problem 2

     if(a[i]=='[=10=]'||b[i]=='[=10=]'){
        return 0;
     }
     if(lcs1[i][j]!=-1)
        return lcs1[i][j];
     else if (a[i]==b[j])
        temp = 1+lcs(i+1,j+1);
     else
        temp = max(lcs(i+1,j),lcs(i,j+1));
     lcs1[i][j] = temp;
     return temp;

 }
 int main(){
     memset(lcs1,-1,sizeof(lcs1));  // problem 1
     int temp = lcs(0,0);
     printf("%d",temp);

 }

_{注意：最好避免使用全局变量。尝试将它们封装在结构或类中。请参阅@Matthieu Brucher 的正确 C++ 实现答案。}

Answer 2

只是为了好玩，使用类:

的 C++17 实现

#include <iostream>
#include <vector>
#include <string_view>

class LCSMemoizer
{
    std::vector<std::vector<int>> memory;
    std::string_view s1;
    std::string_view s2;

public:
    LCSMemoizer(std::string_view s1, std::string_view s2)
    : memory(s1.size(), std::vector<int>(s2.size(), -1)), s1(s1), s2(s2)
    {
    }

    int run(unsigned int i1, unsigned int i2)
    {
        if(i1 == s1.size() || i2 == s2.size())
        {
            return 0;
        }
        if(memory[i1][i2] != -1)
        {
            return memory[i1][i2];
        }
        int sub = 0;
        if(s1[i1] == s2[i2])
        {
            sub = run(i1+1, i2+1);
            sub += 1;
        }
        else
        {
            sub = std::max(run(i1, i2+1), run(i1+1, i2));
        }
        memory[i1][i2] = sub;
        return sub;
    }
};

int lcs(std::string_view s1, std::string_view s2)
{
    LCSMemoizer m(s1, s2);

    return m.run(0, 0);
}

int main()
{
    std::cout << lcs("bd", "abcd");
}

另请注意，通常的问题不仅仅是 return 计数，还有字符串本身。

使用记忆的最长公共子序列

longest common subsequence using memoization

c++

dynamic-programming

memoization