题目：最长回文子串
给你一个字符串 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);
}
总结：先写普通递归，通过普通递归推演动态规划
