最长回文子串是LeetCode中字符串模块的典型题目，要求在给定的字符串中找到最长的回文连续子串。回文串指的是正读和反读都相同的字符串，比如"aba"、"bb"都是回文串。动态规划法通过保存中间计算结果，避免重复判断子串是否为回文，是解决该问题的优质方案。
动态规划核心思路
动态规划解决该问题的核心是将大问题拆解为小问题，通过子问题的解推导原问题的解。我们需要先明确几个关键要素：
状态定义
定义二维数组dp[i][j]，表示字符串中从索引i到索引j的子串（包含i和j）是否为回文串。如果是回文串，dp[i][j]为true，否则为false。
状态转移方程
对于dp[i][j]的取值，需要分情况讨论：
- 如果i == j，说明子串只有一个字符，必然是回文串，
dp[i][j] = true - 如果j - i == 1，说明子串有两个字符，只要这两个字符相同就是回文串，
dp[i][j] = (s[i] == s[j]) - 如果j - i > 1，子串长度大于2，那么
dp[i][j]为true的条件是：s[i] == s[j]，并且dp[i+1][j-1]为true，也就是去掉首尾字符后的子串也是回文串
遍历顺序
因为dp[i][j]依赖dp[i+1][j-1]，也就是依赖左下角的结果，所以遍历的时候需要先遍历子串长度，再遍历起始索引i，这样能保证计算dp[i][j]时，dp[i+1][j-1]已经计算完成。
完整代码实现
以下是Java语言的实现代码，包含完整的逻辑和注释：
public class LongestPalindrome {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
// 字符串长度小于2，直接返回原字符串
return s;
}
// 定义dp数组
boolean[][] dp = new boolean[n][n];
int maxLen = 1; // 最长回文子串长度，初始为1
int begin = 0; // 最长回文子串的起始索引
// 初始化：单个字符都是回文串
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 遍历子串长度，从2开始到n
for (int len = 2; len <= n; len++) {
// 遍历起始索引i
for (int i = 0; i < n; i++) {
int j = i + len - 1; // 结束索引j
// 如果j超出字符串范围，结束当前循环
if (j >= n) {
break;
}
// 判断s[i]和s[j]是否相等
if (s.charAt(i) != s.charAt(j)) {
dp[i][j] = false;
} else {
// 两个字符相等的情况
if (len <= 2) {
// 子串长度为2，直接为true
dp[i][j] = true;
} else {
// 依赖左下角的结果
dp[i][j] = dp[i + 1][j - 1];
}
}
// 如果当前子串是回文串，且长度大于当前最大长度，更新结果
if (dp[i][j] && len > maxLen) {
maxLen = len;
begin = i;
}
}
}
// 截取最长回文子串返回
return s.substring(begin, begin + maxLen);
}
}
复杂度分析
该动态规划解法的时间复杂度和空间复杂度如下：
| 复杂度类型 | 数值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n²) | 需要遍历所有子串，子串总数为n*(n-1)/2，量级为n² |
| 空间复杂度 | O(n²) | 需要存储n*n的二维dp数组 |
常见问题说明
很多开发者在实现时会遇到遍历顺序错误的问题，导致dp[i+1][j-1]还未计算就使用，得到错误结果。一定要遵循先遍历子串长度，再遍历起始索引的顺序，保证依赖的状态已经计算完成。
另外，初始化时只需要初始化单个字符的状态，两个字符及以上的状态会在遍历过程中计算，不需要提前初始化，避免冗余操作。
动态规划法的优势在于逻辑清晰，容易理解，适合作为求解最长回文子串的基础方法，掌握该方法后也可以进一步学习中心扩展法、Manacher算法等更优的解法。
动态规划最长回文子串LeetCode题解字符串处理修改时间：2026-07-03 21:18:32