I am aware of solutions that uses the bottom up dynamic programing approach to solve this problem in O(n^2). I am specifically looking for a top down dp approach. Is it possible to achieve longest palindromic substring using a recursive solution?
Here is what I have tried but it fails for certain cases, but I feel I am almost on the right track.
#include <iostream>
#include <string>
using namespace std;
string S;
int dp[55][55];
int solve(int x,int y,int val)
{
if(x>y)return val;
int &ret = dp[x][y];
if(ret!=0){ret = val + ret;return ret;}
//cout<<"x: "<<x<<" y: "<<y<<" val: "<<val<<endl;
if(S[x] == S[y])
ret = solve(x+1,y-1,val+2 - (x==y));
else
ret = max(solve(x+1,y,0),solve(x,y-1,0));
return ret;
}
int main()
{
cin >> S;
memset(dp,0,sizeof(dp));
int num = solve(0,S.size()-1,0);
cout<<num<<endl;
}
For this case:
if(S[x] == S[y])
ret = solve(x+1,y-1,val+2 - (x==y));
it should be:
if(S[x] == S[y])
ret = max(solve(x + 1, y - 1, val + 2 - (x==y)), max(solve(x + 1, y, 0),solve(x, y - 1, 0)));
Because, in case you cannot create a substring from x to y, you need to cover the other two cases.
Another bug:
if(ret!=0){ret = val + ret;return ret;}
you should return ret + val
and not modify ret
in this case.
The main problem is you store the final val
into dp[x][y]
, but this is not correct.
Example:
acabc , for x = 1 and y = 1, val = 3, so dp[1][1] = 3
, but actually, it should be 1.
Fix:
int solve(int x,int y)
{
if(x>y)return 0;
int &ret = dp[x][y];
if(ret!=0){return ret;}
if(S[x] == S[y]){
ret = max(max(solve(x + 1, y),solve(x, y - 1)));
int val = solve(x + 1, y - 1);
if(val >= (y - 1) - (x + 1) + 1)
ret = 2 - (x == y) + val;
}else
ret = max(solve(x+1,y),solve(x,y-1));
return ret;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With