动态规划 区间dp

设f[i][j]为[i,j]能够形成回文串，如果s[i] == s[j] && (i + 1 > j - 1 || f[i + 1][j - 1])，那么即为回文串
i + 1 > j - 1：形如aa这样的形式
f[i + 1][j - 1]：更一般的形式 abba

import java.util.*;
/*
   区间dp
*/
public class Solution {
    public int getLongestPalindrome(String A, int n) {
        boolean f[][] = new boolean[n + 10][n + 10];
        for(int i = 0;i < n;i++)f[i][i] = true;
        int res = 1;
        for(int len = 2;len <= n;len++){
            for(int i = 0;i < n;i++){
                int j = i + len - 1;
                if(j >= n)continue;
                if(A.charAt(i) == A.charAt(j)){
                    if(i + 1 > j - 1 || f[i + 1][j - 1]){
                        f[i][j] = true;
                        res = Math.max(res,len);
                    }
                }
            }
        }
        return res;
    }
}

O(n^2) O(n^2)