思路：暴力队腐，動(dòng)態(tài)規(guī)劃求解
最終方案：python動(dòng)態(tài)規(guī)劃超時(shí)，c++可以
image.png
abccbad,這個(gè)字符串的最長回文子串薪前，可以通過動(dòng)態(tài)規(guī)劃的方式來做润努。
- 按列遍歷上三角，因?yàn)榍骯[i][j]需要知道a[i+1][j-1]的值示括，來確定上一個(gè)字符是否已經(jīng)是回文
- 如果子字符串的長度小于等于3铺浇，或者前一個(gè)字符的串是否是回文，標(biāo)為1
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int main()
{
string s="abccbad";
int str_len=s.length();
int **p=new int* [str_len];
for(int i=0;i<str_len;i++){
p[i]=new int[str_len];
}
for(int i=0;i<str_len;i++){
for(int j=0;j<str_len;j++){
p[i][j]=0;
if(i==j){
p[i][j]=1;
}
}
}
int max_begin=0;
int max_len=1;
for(int j=1;j<str_len;j++){
for(int i=0;i<j;i++){
if(s[i]==s[j]){
if(j-i+1<=3 || p[i+1][j-1]==1){
p[i][j]=1;
}
}
if(p[i][j]==1 && j-i+1>max_len){
max_len=j-i+1;
max_begin=i;
}
}
}
for(int i=0;i<str_len;i++){
for(int j=0;j<str_len;j++){
cout<<p[i][j]<<" ";
}
cout<<endl;
}
cout<<s.substr(max_begin,max_len)<<endl;
return 0;
}
