सबसे लंबा पालिंड्रोमिक सबस्ट्रिंग रिकर्सिव समाधान

Question

मुझे उन समाधानों से अवगत है जो ओ (एन^2) में इस समस्या को हल करने के लिए नीचे गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करते हैं। मैं विशेष रूप से शीर्ष नीचे डीपी दृष्टिकोण की तलाश में हूं। क्या एक पुनरावर्ती समाधान का उपयोग करके सबसे लंबे समय तक पैलिंड्रोमिक सबस्ट्रिंग प्राप्त करना संभव है?

यहां मैंने जो कोशिश की है, लेकिन यह कुछ मामलों के लिए विफल रहता है, लेकिन मुझे लगता है कि मैं लगभग सही रास्ते पर हूं।

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

यह होना चाहिए:

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

वजह से, मामले में आप X से Y तक सबस्ट्रिंग नहीं बना सकते, तो आप अन्य दो को कवर करने की जरूरत है मामलों।

एक और बग:

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

आप return ret + val और नहीं इस मामले में ret संशोधित करना चाहिए।

मुख्य समस्या यह है कि आप अंतिम val को dp[x][y] पर संग्रहीत करते हैं, लेकिन यह सही नहीं है।

उदाहरण:

acabc, एक्स = 1 और y = 1, वैल = 3, इसलिए dp[1][1] = 3, लेकिन वास्तव में के लिए, यह होना चाहिए 1.

फिक्स: पर

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