在字符串算法领域，寻找“最长回文子串”是一个经典且富有挑战性的问题。LeetCode最长回文子串动态规划解法之所以备受推崇，其核心价值在于它完美地展示了如何将“判断任意子串是否为回文”这一重叠子问题，通过动态规划（DP）进行记忆化存储，从而将时间复杂度从暴力法的O(n³)优化至O(n²)，并提供了一个清晰、可扩展的算法框架。理解这一解法，不仅是掌握一道题目，更是深入理解动态规划中“状态定义”与“状态转移”艺术的关键一步。作为鳄鱼Java的资深内容编辑，我将为你系统性地剖析这一解法的每一个细节，从暴力破解到DP优化，从状态方程到代码实现。
一、问题重述与暴力解法的瓶颈
问题描述：给定一个字符串 `s`，找到 `s` 中最长的回文子串。假设字符串的最大长度为 1000。
回文串定义： 正读和反读都一样的字符串。
最直观的暴力解法： 枚举所有可能的子串（起点 `i` 和终点 `j`），然后检查每个子串是否为回文。
1. 子串数量级：O(n²)。
2. 检查每个子串是否为回文：O(子串长度) = O(n)。
总时间复杂度高达 O(n³)，对于 n=1000 的边界条件完全不可接受。其根本瓶颈在于，判断 `s[i..j]` 是否为回文时，我们重复判断了许多更短的子串（如 `s[i+1..j-1]`）。
这自然引出了动态规划的核心思想：利用已知的子问题解，来避免重复计算。
二、动态规划解法的核心思想：状态定义与转移
LeetCode最长回文子串动态规划解法的精髓在于定义一个二维DP数组，并找到子问题间的递推关系。
1. 状态定义
定义 `dp[i][j]` 为一个布尔值（boolean），表示字符串 `s` 中从索引 `i` 到索引 `j` 的闭区间子串 `s[i..j]` 是否为回文串。
- `dp[i][j] = true`： 子串 `s[i..j]` 是回文。
- `dp[i][j] = false`： 子串 `s[i..j]` 不是回文。
2. 状态转移方程（递推关系）
如何由更小的子问题推导出 `dp[i][j]` 的值？考虑回文串的性质：
- 如果一个字符串是回文串，那么去掉首尾两个字符后，剩下的子串也一定是回文串。
- 反之，如果已知中间子串是回文，且首尾字符相等，那么整个字符串就是回文。
因此，转移方程为：
dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1]
解读： 子串 `s[i..j]` 是回文，当且仅当：
1. 其首尾字符 `s[i]` 和 `s[j]` 相等。
2. 其去掉首尾后的内部子串 `s[i+1..j-1]` 也是回文（即 `dp[i+1][j-1]` 为 true）。
3. 边界条件（递推的起点）
上述转移方程在 `j - i <= 2` 时，即子串长度为 1、2 或 3 时，需要特殊处理，因为此时 `s[i+1..j-1]` 不是一个有效的区间或长度很小：
- **长度为1** (`i == j`)： 单个字符自然是回文。`dp[i][i] = true`。
- **长度为2** (`j == i + 1`)： 两个字符是回文，当且仅当它们相等。即 `dp[i][i+1] = (s[i] == s[i+1])`。
- **长度为3** (`j == i + 2`)： 三个字符是回文，当且仅当首尾字符相等（此时中间字符无需判断）。这实际上被 `(s[i]==s[j]) && dp[i+1][j-1]` 覆盖了，因为当 `j=i+2` 时，`dp[i+1][j-1]` 就是 `dp[i+1][i+1]`，恒为 true。
因此，边界条件可以统一为：当子串长度（j-i）小于3时，只要首尾字符相等，它就是回文。这可以简洁地表达为：dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i <= 2 || dp[i+1][j-1])。
这就是LeetCode最长回文子串动态规划解法的数学核心，在鳄鱼Java社区的算法精讲中，这个状态转移方程的推导是重中之重。
三、Java代码实现与遍历顺序的奥秘
理解了状态定义和转移方程，代码实现的关键在于正确的填表顺序。因为 `dp[i][j]` 依赖于 `dp[i+1][j-1]`（左下角的值），我们必须保证在计算 `dp[i][j]` 时，它所依赖的子问题已经被计算并存储。
正确的遍历方式：按子串长度递增遍历
```java class Solution { public String longestPalindrome(String s) { int n = s.length(); if (n < 2) return s;
boolean[][] dp = new boolean[n][n];
int maxLen = 1; // 最长回文子串的长度
int start = 0; // 最长回文子串的起始索引
// 初始化：所有长度为1的子串都是回文
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 开始递推，按子串长度L从小到大遍历（L从2到n）
for (int L = 2; L <= n; L++) {
// 枚举子串的起始位置i
for (int i = 0; i <= n - L; i++) {
int j = i + L - 1; // 子串的结束位置j
// 首尾字符是否相等？
if (s.charAt(i) != s.charAt(j)) {
dp[i][j] = false;
} else {
// 首尾字符相等，根据子串长度判断
if (L <= 3) { // 长度<=3时，无需看内部子串
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1]; // 状态转移
}
}
// 如果是回文，且长度超过当前最大值，则更新记录
if (dp[i][j] && L > maxLen) {
maxLen = L;
start = i;
}
}
}
return s.substring(start, start + maxLen);
}
}
<p><strong>关键点解析</strong>：<br>
1. **外循环是长度L**： 这确保了当我们计算长度为L的子串时，所有长度小于L的子串（特别是 `dp[i+1][j-1]`，其长度为L-2）都已经被计算出来了。<br>
2. **内循环是起点i**： 对于每个固定长度L，遍历所有可能的起点。<br>
3. **条件判断的精简**： 代码中将边界条件 `L <= 3` 单独处理，逻辑更清晰。</p>
<h2>四、复杂度分析与对比：DP的优势与代价</h2>
<p><strong>时间复杂度：O(n²)**。
- 我们需要填充一个 n x n 的二维DP表格，每个状态 `dp[i][j]` 的计算是 O(1) 的。<br>
- 因此总时间复杂度为 **O(n²)**。</p>
<p><strong>空间复杂度：O(n²)**。
- 我们需要一个 n x n 的二维布尔数组来存储所有子问题的解。</p>
<p><strong>对比其他主流解法</strong>：</p>
<table border="1">
<tr><th>解法</th><th>时间复杂度</th><th>空间复杂度</th><th>核心思想</th></tr>
<tr><td>暴力枚举</td><td>O(n³)</td><td>O(1)</td><td>枚举所有子串并验证</td></tr>
<tr><td><strong>动态规划（本文核心）</strong></td><td><strong>O(n²)</strong></td><td><strong>O(n²)</strong></td><td><strong>记忆化子问题，避免重复计算</strong></td></tr>
<tr><td>中心扩散法</td><td>O(n²)</td><td>O(1)</td><td>枚举所有中心，向两边扩展</td></tr>
<tr><td>Manacher算法</td><td>O(n)</td><td>O(n)</td><td>利用回文对称性，线性时间</td></tr>
</table>
<p><strong>动态规划的优劣</strong>：<br>
- **优势**： 思路清晰，是学习动态规划的绝佳例题。它系统地解决了所有子问题，并且可以方便地记录和查询任意子串是否为回文。<br>
- **劣势**： 空间复杂度较高，为O(n²)。对于追求极致性能的场景，中心扩散法（O(1)空间）或Manacher算法（O(n)时间）更优。但在面试和多数实践中，<strong>LeetCode最长回文子串动态规划</strong>解法因其普适性和教育意义，仍然具有极高价值。</p>
<h2>五、关键细节与优化思考</h2>
<p><strong>1. 遍历顺序的必然性</strong><br>
为什么必须按长度遍历？因为状态转移方程 `dp[i][j] = ... dp[i+1][j-1]` 表明，当前状态依赖于“左下角”的状态。如果我们按 `i` 从0到n，`j` 从0到n 的简单双重循环，计算 `dp[i][j]` 时 `dp[i+1][j-1]` 可能还未计算，导致错误。</p>
<p><strong>2. 空间复杂度优化（可选）</strong><br>
观察状态转移方程，`dp[i][j]` 只依赖于下一行 (`i+1`) 的左下角数据。因此，我们可以将二维DP数组优化为<strong>一维滚动数组</strong>，将空间复杂度从 O(n²) 降至 O(n)。但这会稍微增加代码的理解难度，在面试中清晰地解释二维解法通常已足够。</p>
<p><strong>3. 初始化与边界处理</strong><br>
代码中显式初始化了 `dp[i][i] = true`（长度为1的回文）。在后续递推中，对于长度L=2和L=3的情况，我们通过 `L <= 3` 这个条件统一处理，逻辑更紧凑。</p>
<p><strong>4. 记录结果的方式</strong><br>
我们并非在最后遍历整个DP表寻找最大值，而是在填充每个 `dp[i][j]` 时，实时更新最长回文子串的起始位置 `start` 和长度 `maxLen`。这避免了二次遍历，是常见的优化技巧。</p>
<h2>六、从理论到实践：动态规划思想的延伸</h2>
<p>掌握<strong>LeetCode最长回文子串动态规划</strong>解法，其意义远超出本题。它训练了一种重要的算法设计思维：</p>
<p><strong>1. 识别重叠子问题</strong>： 判断不同起止点的子串是否为回文，大量中间子串被重复判断。<br>
<strong>2. 定义无后效性的状态</strong>： `dp[i][j]` 仅表示子串 `s[i..j]` 是否为回文，这个状态本身包含了解决问题所需的全部信息，其值一旦确定就不再改变，且后续决策不依赖其历史路径。<br>
<strong>3. 建立状态转移方程</strong>： 这是动态规划的灵魂，找到如何用已知的小问题解来构建大问题解。<br>
<strong>4. 确定正确的计算顺序</strong>： 确保在计算每个状态时，它所依赖的子状态都已被计算。</p>
<p>这种思维可以应用到无数其他场景，例如：<br>
- **编辑距离（LeetCode 72）**： 定义 `dp[i][j]` 为将 word1 前 i 个字符转换为 word2 前 j 个字符的最小操作数。<br>
- **最长公共子序列（LeetCode 1143）**： 定义 `dp[i][j]` 为 text1 前 i 个字符和 text2 前 j 个字符的LCS长度。<br>
- **背包问题**： 定义 `dp[i][j]` 为考虑前 i 个物品，在容量 j 下的最大价值。</p>
<p>在鳄鱼Java社区的项目实战讨论中，动态规划思想也常用于解决资源调度、路径规划等复杂决策问题。</p>
<h2>总结与思考</h2>
<p><strong>LeetCode最长回文子串动态规划</strong>解法，如同一把精致的钥匙，为我们打开了用系统化、表格化的方式解决复杂字符串问题的大门。它教会我们的不是机械地填表，而是如何将一个问题分解为相互关联的子问题，并通过记忆化来消除冗余计算。</p>
<p>现在，请你思考：你是否能脱离代码，在白板上清晰地画出DP表格的填充过程？你是否理解了为什么中心扩散法在空间上更优，而动态规划在思路上更具一般性？当你下次遇到诸如“最长回文子序列”或“分割回文串”等问题时，能否敏锐地意识到它们与本题共享着相同的动态规划基因？算法的魅力在于其通用性，一道题的深刻理解，足以照亮一类问题的求解之路。如果你对更多动态规划经典问题及其在工程中的应用感兴趣，欢迎持续深入鳄鱼Java社区的算法与数据结构专栏，与我们一同探索。</p>
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
