самая длинная общая подпоследовательность, использующая запоминание

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]=='\0'||b[i]=='\0'){
        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

Просто для удовольствия, реализация 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");
}

Также обратите внимание, что обычный вопрос заключается не только в возврате счетчика, но и самой строки.

Answer 2

2 проблемы:

• вы инициализировали массив памятки после вызова lcs()
• у вас было дополнительно if в начале вашего lcs()

Вот исправленный код:

#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]=='\0'||b[i]=='\0'){
        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 ++.}