思路：暴力，動態(tài)規(guī)劃求解

最終方案：python動態(tài)規(guī)劃超時，c++可以

image.png

abccbad,這個字符串的最長回文子串，可以通過動態(tài)規(guī)劃的方式來做。

1. 按列遍歷上三角，因為求a[i][j]需要知道a[i+1][j-1]的值，來確定上一個字符是否已經(jīng)是回文
2. 如果子字符串的長度小于等于3，或者前一個字符的串是否是回文，標為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;
}