längste palindromische Teilzeichenfolge rekursive Lösung

Question

Ich bin mir der Lösungen bewusst, die den Bottom-up-Ansatz zur dynamischen Programmierung verwenden, um dieses Problem in O (n^2) zu lösen. Ich suche speziell nach einem Top-Down-DP-Ansatz. Ist es möglich, mit einer rekursiven Lösung die längste palindromische Teilkette zu erhalten?

Hier ist, was ich versucht habe, aber es scheitert für bestimmte Fälle, aber ich fühle mich fast auf dem richtigen Weg.

#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

Für diesen Fall:

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

es sein sollte:

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

Da im Fall können Sie nicht einen Teil von x nach y erstellen, müssen Sie die beide andere zur Deckung Fälle.

Ein weiterer Fehler:

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

Sie sollten return ret + val und nicht ret in diesem Fall ändern. Das Hauptproblem ist, dass Sie das letzte val in dp[x][y] speichern, aber das ist nicht korrekt.

Beispiel:

acabc, für x = 1 und y = 1, val = 3, so dp[1][1] = 3, aber eigentlich sollte es sein, 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; 
}