本文详解如何通过动态规划优化暴力枚举回文子串的低效实现，将时间复杂度从原始代码隐含的 o(n³)（实际为 o(n²) 字符串操作 × o(n) 反转）降至真正稳定的 o(n²)，并给出可直接落地的 java 实现与关键避坑指南。
本文详解如何通过动态规划优化暴力枚举回文子串的低效实现，将时间复杂度从原始代码隐含的 o(n³)（实际为 o(n²) 字符串操作 × o(n) 反转）降至真正稳定的 o(n²)，并给出可直接落地的 java 实现与关键避坑指南。
原始代码存在多重性能瓶颈：
- 外层双指针嵌套循环（i, k）本质是枚举所有子串，时间复杂度 O(n²)；
- 每次调用 substring() + StringBuilder.reverse() 构造并比对反转字符串，单次操作最坏达 O(n)，导致整体时间复杂度飙升至 O(n³)；
- 循环逻辑混乱（如 k=i 重置方式易引发边界错误），且未利用回文的递推性质。
✅ 正确解法：区间 DP（动态规划）
核心思想：长度为 len 的子串 s[i..j] 是回文 ⇔ s[i] == s[j] 且 s[i+1..j−1] 是回文（或 len ≤ 2）。
我们用二维布尔数组 dp[i][j] 表示子串 s.substring(i, j+1) 是否为回文，按子串长度从小到大、或按起始位置从后往前填充，确保子问题已求解。
以下是优化后的 Java 实现（返回最长回文子串，时间 O(n²)，空间 O(n²)）：
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) return s;
int n = s.length();
boolean[][] dp = new boolean[n][n];
int start = 0, maxLength = 1; // 记录最长回文的起始索引和长度
// 单字符均为回文
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 枚举子串长度 len = 2 到 n
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1; // 子串结束索引
if (s.charAt(i) == s.charAt(j)) {
if (len == 2) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && len > maxLength) {
start = i;
maxLength = len;
}
}
}
return s.substring(start, start + maxLength);
}? 关键优化点解析：
- 避免字符串拷贝与反转：仅比较字符 charAt(i) 和 charAt(j)，时间降为 O(1)；
- 状态复用：dp[i][j] 直接复用 dp[i+1][j−1] 结果，消除重复计算；
- 清晰的循环顺序：先固定长度再滑动窗口，逻辑严谨，边界安全；
- 空间可进一步优化：若只需长度无需子串，可用一维 DP；若需输出子串，O(n²) 空间合理。
⚠️ 注意事项：
- 原始代码中 str 变量名与参数 s 不一致，属编译错误，需统一；
- substring(i, k) 的右边界 k 是开区间，务必与 dp[i][j] 定义（闭区间）对齐；
- 对于空串或单字符输入，必须提前返回，避免数组越界；
- 若题目要求“任意一个回文子串”（非最长），可在首次 dp[i][j] == true 时立即返回，进一步剪枝。
总结：回文子串问题的经典优化路径是「暴力枚举 → 中心扩展（O(n²) 时间/O(1) 空间）→ 区间 DP（O(n²) 时间/O(n²) 空间，易于理解与扩展）」。本文提供的 DP 方案在可读性、正确性与工程实用性上取得良好平衡，是面试与实际开发中的推荐解法。
