najdłuższe rozwiązanie rekurencyjne podstrukturowania palindromowego

Question

Jestem świadomy rozwiązań, które używają oddolnego programowania dynamicznego, aby rozwiązać ten problem w O (n^2). W szczególności szukam podejścia od góry do dołu. Czy możliwe jest uzyskanie najdłuższego substratu palindromowego za pomocą rekurencyjnego rozwiązania?

Oto, co próbowałem, ale w niektórych przypadkach się nie udało, ale czuję, że jestem na dobrej drodze.

#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; 
} 

Answer 1

W tym przypadku:

if(S[x] == S[y]) 
    ret = solve(x+1,y-1,val+2 - (x==y)); 

powinno być:

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))); 

powodu, w przypadku, gdy nie można utworzyć podciąg od x do y, trzeba pokryć pozostałe dwa przypadki.

Kolejny błąd:

if(ret!=0){ret = val + ret;return ret;} 

należy return ret + val i nie modyfikować ret w tym przypadku.

Głównym problemem jest przechowywanie ostatecznego val w dp[x][y], ale nie jest to poprawne.

przykład:

acabc dla x = 1, y = 1, Val = 3, tak dp[1][1] = 3, ale w rzeczywistości, powinna wynosić 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; 
}