hello world!(你好,世界)
想要了解这题的动态规划,提议先了解这题的"中心扩散法"
解题思路：

最长回文子串的中心扩散法，遍历每个字符作为中间位，进行左右比较

算法流程：

从右到左，对每个字符进行遍历处理，并且每个字符要处理两次，因为回文子串有两种情况：
ABA型：只需要从当前字符向两边扩散，比较左右字符是否相等，找出以当前字符为中心的最长回文子串长度
ABBA型：只需要从当前字符和下一个字符向两边扩散，比较左右字符是否相等，找出以当前字符和下一个字符为中心的最长回文子串长度
最后比对两种类型的长度，取自较长的长度
Java 版本代码如下：

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();System.out.println(solution(s));}private static int solution(String s) {int res = 0;for(int i = 0; i < s.length(); i++) {// ABA型int len1 = longest(s, i, i);// ABBA型int len2 = longest(s, i, i + 1);res = Math.max(res, len1 > len2 ? len1 : len2);}return res;}private static int longest(String s, int l, int r) {while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {l--;r++;}return r - l - 1;}
}

在这里你应该明白了边界条件为啥要r-l>=2 因为aa型需要r-l>=1,而aba型需要r-l>=2

动态规划:

在0 ~ n-1的字符串上,让i为0 ~ n-1上某个值
j在0 ~ i上滑动,判断子串0 ~ j里面的回文最长为多少.
直至最后一个子问题dp[j][i]也得到结果

public static void main(String[] args) {Scanner scanner=new Scanner(System.in);String s=scanner.nextLine();System.out.println(validLen(s));}public static int validLen(String s) {int n=s.length();// 状态：对比的两个字符索引起始和终止索引位置// 定义: 字符串s的i到j字符组成的子串是否为回文子串boolean[][] dp=new boolean[n][n];//因为从i到i的单字母也是回文for(int i=0;i