动态规划是解决最长回文子串问题最经典且高效的方法之一，时间复杂度o(n²)，空间复杂度可优化至o(n)；核心利用回文对称性，定义dpi表示s[i..j]是否为回文，并按子串长度从小到大递推更新状态，同时记录最大长度与起始位置。

动态规划是解决最长回文子串问题最经典且高效的方法之一，时间复杂度 O(n²)，空间复杂度可优化到 O(n)。核心在于利用回文的对称性：如果 s[i] == s[j]，且 s[i+1..j-1] 是回文，那么 s[i..j] 也是回文。

状态定义与转移方程

定义 dp[i][j] 表示子串 s[i..j] 是否为回文（boolean 类型），则：

• 当 i == j 时，单个字符必为回文 → dp[i][i] = true
• 当 j == i + 1 时（长度为 2），只需判断 s[i] == s[j]
• 当 j > i + 1 时，dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

每次更新 dp[i][j] 后，若为 true，记录当前长度和起始位置，用于最后截取结果。

二维 DP 的标准实现（易理解）

用二维布尔数组存储状态，按子串长度从小到大枚举，避免依赖未计算的状态：

deep-java-review

Java项目代码review工具。分析Git变更+完整调用链路上下文，推断业务需求，进行多维度评分和分类汇总，生成完整PRD文档。包含细粒度Java代码审查清单（Null安全、异常处理、Streams、并发、equals/hashCode、资源管理、API设计、性能、MyBatis/ORM、事务边界、SQL/DD...

下载

• 先初始化所有长度为 1 的子串（dp[i][i] = true）
• 再处理长度为 2 的子串（i 从 0 到 n-2，j = i+1）
• 最后枚举长度 L 从 3 到 n，i 从 0 到 n-L，j = i+L-1
• 每次满足 s[i]==s[j] 且 dp[i+1][j-1] 为 true 时更新最大长度和起始索引

空间优化：滚动数组或一维 DP

由于 dp[i][j] 只依赖 dp[i+1][j-1]（即左下角），无法直接压缩成严格一维，但可只保留上一层（i+1 对应的行）来节省空间。更常用的是「中心扩展法」配合 DP 思想做空间 O(1) 解法；若坚持 DP，可用两个一维数组交替更新，把空间降到 O(n)。

边界与细节处理

容易出错的地方包括：

• 循环顺序必须保证 dp[i+1][j-1] 已计算 → 推荐按长度枚举，而非简单双重 for(i,j)
• 字符串为空或长度为 1 时需特判，返回原串
• 更新最大长度时，要同步更新起始下标：start = i，maxLen = j - i + 1
• Java 中 substring(i, j) 是左闭右开，最终返回 s.substring(start, start + maxLen)

不复杂但容易忽略细节，写完建议用 "babad"、"cbbd"、"a"、"" 几个典型用例验证。

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南