最长的回文子串递归解-Java 学习之路

我知道使用自下而上动态编程方法的解决方案在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;
}

2 回答

/*C++ program to print the largest palindromic string present int the given string
eg. "babad" contains "bab" and "aba" as two largest substring.
by occurance, "bab" comes first hence print "bab".
*/

#include<bits/stdc++.h>
using namespace std;
bool ispalindrome(string s)
{
    int l = s.length()-1;
    int r = 0;
    while(l>r){
        if(s[l]!=s[r])
            return false;
        l--;r++;
    }
    return true;
}
int main()
{
    string str,str1,str3;
    vector<string> str2;
    cin>>str;
    int len = str.length();
    for(int i=0;i<len;i++)
    {
        for(int j=i;j<=len;j++)
        {
            str1 = "";
            str1.append(str,i,j);
            if(ispalindrome(str1)){
                str2.push_back(str1);
            }
        }
    }
    int max = 0;
    for(int i=0;i<str2.size();i++)
    {
        if(str2[i].length()>max){
            max = str2[i].length();
            str3 = str2[i];
        }
    }
    cout<<"MAXIMUM LENGTH IS : "<<max<<"\nLARGEST PALINDROMIC STRING IS : "<<str3<<endl;
    return 0;
}

回复于 2024-05-01T23:23:02+08:00

对于这种情况：

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

回复于 2024-05-01T23:23:02+08:00

最长的回文子串递归解

2 回答

相关问题