soluzione ricorsiva di sottostringa palindromica più lunga

Question

Sono a conoscenza di soluzioni che utilizzano l'approccio di programmazione dinamico bottom-up per risolvere questo problema in O (n^2). Sto specificatamente cercando un approccio top down down. È possibile ottenere una sottostringa palindromica più lunga utilizzando una soluzione ricorsiva?

Ecco cosa ho provato ma non riesce in alcuni casi, ma sento che sono quasi sulla strada giusta.

#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

Per questo caso:

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

dovrebbe essere:

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

Perché, nel caso in cui non è possibile creare una stringa da X a Y, è necessario coprire gli altri due casi.

altro bug:

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

si dovrebbe return ret + val e non modificare ret in questo caso.

Il problema principale è memorizzare l'val finale in dp[x][y], ma questo non è corretto.

Esempio:

acabc, per x = 1 ey = 1, val = 3, così dp[1][1] = 3, ma in realtà, dovrebbe essere 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; 
}