en uzun palindromik alt dizgi özyinelemeli çözüm

Question

Bu sorunu çözmek için aşağıdan yukarıya dinamik programlama yaklaşımı kullanan çözümlerden haberdarım O (n^2). Özellikle yukarıdan aşağıya bir dp yaklaşımı arıyorum. Yinelemeli bir çözüm kullanarak en uzun palindromik substring elde etmek mümkün mü?

İşte denedim ama bazı durumlarda başarısız oluyor, ama neredeyse doğru yolda olduğumu hissediyorum. Bu durum için

#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

:

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

olması gerektiği: durumda y x bir alt dizeyi oluşturamazsınız

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

, olduğundan, diğer iki kapak gerek vakalar.

Başka hata: Eğer return ret + val ve bu durumda değil ret değiştirmesi gerektiğini

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

.

Ana sorun, son valdp[x][y] içine saklamak, ancak bu doğru değil.

Örnek:

acabc, aslında x = 1 ve y = 1, val = 3, bu dp[1][1] = 3 edilmiş, ancak olması gerektiği 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; 
}