最长回文子串递归解

一尘不染

最长回文子串递归解

algorithm

我知道使用自底向上动态编程方法来解决O（n ^ 2）中此问题的解决方案。我特别在寻找一种自上而下的dp方法。是否可以使用递归解决方案来获得最长回文子串？

这是我尝试过的方法，但是在某些情况下失败了，但是我觉得自己几乎是对的。

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

阅读 389

2020-07-28

共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，对于x = 1和y = 1，val = 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;
}

2020-07-28