题目：最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

思路：

定义状态：dp[i][j]表示字符串s从索引i到j的子串是否是回文
状态转移方程：
如果s.charAt(i) == s.charAt(j)，那么dp[i][j] = dp[i+1][j-1]
否则dp[i][j] = false
边界条件：
单个字符总是回文：dp[i][i] = true
两个相同字符也是回文：dp[i][i+1] = (s.charAt(i) == s.charAt(i+1))

题解：

1.普通递归实现（会超时）

//递归方式实现public static String longestPalindromic(String s){if(s == null || s.length() <= 1){return s;}int len = s.length();//判断整个字符串是不是回文串if(isPalindrome(s, 0, len - 1)){return s;}// 递归检查左子串和右子串String a = longestPalindromic(s.substring(1, len));String b = longestPalindromic(s.substring(0, len - 1));// 返回较长的那个子串return a.length() >= b.length() ? a : b;}// 辅助函数：检查子串是否是回文public static Boolean isPalindrome(String s, int left, int right){if(left >= right){return true;}if(s.charAt(left) != s.charAt(right)){return false;}return isPalindrome(s, left + 1, right - 1);}

2.动态规划实现

//动态规划实现public static String dpLongestPalindromic(String s){if(s == null || s.length() <= 1){return s;}int len = s.length();//存储下标范围内的子串是否是回文boolean[][] dp = new boolean[len][len];//记录最长子串的开始位置和最大长度int start = 0;int maxLen = 1;// 每个单独的字符都是回文for (int i = 0; i < len; i++) {dp[i][i] = true;}//先对长度为2的字符串进行逻辑判断，是否满足回文for (int i = 0; i < len - 1; i++) {if(s.charAt(i) == s.charAt(i+1)){dp[i][i+1] = true;start = i;maxLen = 2;}}//当字符串长度 >= 3时for (int length = 3; length <= len; length++) {for (int i = 0; i <= len-length; i++) {int j = i + length - 1;if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1]){dp[i][j] = true;if(length > maxLen){start = i;maxLen = length;}}}}return s.substring(start, start+maxLen);}