Нахождение LCS с использованием DP
Я использовал динамическое программирование, чтобы найти самую длинную общую подпоследовательность ч / б из двух строк. Что не так в коде. Почему он всегда дает ответ как 0?
#include<bits/stdc++.h>
using namespace std;
int dp[20][20];
void initialize()
{
for(int i=0;i<20;i++)
for(int j=0;j<20;j++)
dp[i][j]=-1;
}
int lcs(string a,string b,int m,int n)
{
if(m==0||n==0)
return 0;
if(dp[m][n]!=-1)
return dp[m][n];
if(a[m-1]==b[n-1])
return dp[m-1][n-1] = 1+lcs(a,b,m-1,n-1);
if(a[m-1]!=b[n-1])
return dp[n-1][m-1]=max(dp[n][m-1]=lcs(a,b,n,m-1),dp[n-1][m]=lcs(a,b,n-1,m));
}
int main()
{
string a="AGGTAB",b="GXTXAYB";
cout<<lcs(a,b,a.length(),b.length());
}
Решение
- Вы забыли вызвать initialize ()
- 18-я строка, это должно быть dp [m] [n], а не dp [m-1] [n-1]
- Комментарий 19-й строки кода, так как он не нужен & сделать код совместимым для всех компиляторов
то есть, некоторый компилятор может выдавать предупреждение: управление достигает конца не пустой функции [-Wreturn-type]
- Внесены некоторые изменения в коде в 20-й строке, так как кажется, вы перепутали с переменными m & п.
Код:
#include<bits/stdc++.h>
using namespace std;
int dp[20][20];
void initialize()
{
for(int i=0;i<20;i++)
for(int j=0;j<20;j++)
dp[i][j]=-1;
}
int lcs(string a,string b,int m,int n)
{
if(m==0||n==0)
return 0;
if(dp[m][n]!=-1)
return dp[m][n];
if(a[m-1]==b[n-1])
return dp[m][n] = 1+lcs(a,b,m-1,n-1);
//if(a[m-1]!=b[n-1])
return dp[m][n]=max(lcs(a,b,m-1,n),lcs(a,b,m,n-1));
}
int main()
{
string a="AGGTAB",b="GXTXAYB";
initialize();
cout<<lcs(a,b,a.length(),b.length());
}
Выход:
4
Другие решения
Других решений пока нет …