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

Hier habe ich es versucht, aber es schlägt in bestimmten Fällen fehl, 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;
}