最长回文子串，区间Dp

#include<vector>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <math.h>
#include <queue>
#include <string.h>
using namespace std;
const int N = 1010;
char s[N];
int f[N][N];
int low,high;//标记最长子串的起，尾位置
//状态表示,f[i,j]-表示i,j区间，是否是回文字符串
//数值属性：1表示是，0表示不是
int main(){
    cin>>s;
    int length=strlen(s);
    //单个字符一定是
    for(int i=0;i<length;i++){
        f[i][i]=1;
        low=high=i;
    }
    //状态计算：大区间依赖于小区间如果[i,j]区间是回文子串，那说明[i-1][j-1]也是回文子串
    int maxlen=1;
    for(int len=2 ;len <=length;len++){
        for(int i=0;len+i-1<length;i++){
            int j=len+i-1;
            if(s[i]==s[j]){
                if(len==2){
                    f[i][j]=1;
                }else{
                    f[i][j]=f[i+1][j-1];
                }
            }else{
                f[i][j]=0;
            }
            if (f[i][j]&&maxlen<j-i+1) {
                maxlen=j-i+1;
                low=i;
                high=j;
            }
        }
    }
    for (int i = low; i <= high; i++) {
        printf("%c",s[i]);
    }
    return 0;
}