最长回文子串这道题，可以说是动态规划入门路上绕不过去的一道坎。LeetCode第5题，看起来就是“给一个字符串，找最长的回文子串”，但真上手做的时候，你会发现它特别适合用来理解动态规划的核心思想：状态怎么定义、转移方程怎么推、遍历顺序怎么定。这篇文章我就用刷这道题的完整过程，把动态规划这套思路掰开揉碎讲清楚，适合刚学DP、或者刷题总是“看答案能懂、自己写就废”的朋友。
1. 先搞清楚这道题在干什么
1.1 回文串的本质特征
回文串这个概念其实很简单，就是正着读和倒着读都一样的字符串。比如"aba"、"bb"、"a"都是回文串，而"ab"、"abc"不是。单字符一定是回文串，这一点看起来不起眼，但它恰恰是动态规划里最重要的初始化条件，后面会反复用到。
判断一个字符串是不是回文串，最直观的办法是双指针从两头往中间走，逐个比对字符。但题目要的不是“判断一个串是不是回文”，而是“在一大堆子串里找最长的那个”，这就完全不一样了。如果对每个子串都用双指针判断一次，以"babad"为例，它的所有子串数量是n(n+1)/2个，每个子串判断又要O(n)时间，整体就是O(n³)，字符串一长就彻底跑不动了。所以暴力解法虽然能过示例用例，但从来不是这道题真正的考点。
那动态规划是怎么切入这个问题的呢？核心就一句话：一个长回文串去掉首尾两个字符后，剩下的中间部分必须仍然是回文串。反过来看，如果我们已经知道某个子串是回文串，那在它左右各扩展一个相同字符，得到的新串也一定是回文串。这种“由短推长”的结构，天然就适合动态规划来做。
1.2 为什么暴力解法不够用
我最早刷这道题的时候也想过：能不能用滑动窗口？先把窗口长度从大到小试，每试一个长度就检查一遍有没有回文子串。逻辑上说得通，但仔细一算就会发现问题。窗口长度有n种可能，每种长度下的子串数量又有n个量级，每个子串检查回文还需要O(n)，整体依然是O(n³)，只是常数上好看了一点，本质没有变化。
再说说暴力解法的另一个尴尬之处：大量重复计算。判断"abcba"的时候，我们在开头判断过"bcb"是回文，后面判断"bcb"作为独立子串时又判断了一遍。一个稍长的字符串里，这种重叠子串到处都是，重复的工作太多了。
动态规划解决问题的思路就是把这些重复计算的结果保存下来，用空间换时间。这也是所有动态规划问题的共同出发点：找到重叠子问题，用一张表把中间结果记下来，避免反复算。最长回文子串恰好是一个极佳的示范，因为它的状态转移非常直观，比背包问题更容易理解DP到底是什么、为什么能快起来。
2. 动态规划的思路拆解
2.1 状态定义：从“是什么”开始
动态规划的第一步永远是定义状态。很多初学者卡在这里，不知道该用什么维度去描述一个问题。最长回文子串的状态定义其实很自然：dp[i][j]表示字符串从第i个位置到第j个位置这一段子串，是不是回文串。是就是true，不是就是false，它是一个布尔值的二维数组。
为什么是二维数组而不是一维？因为需要同时记录子串的起点和终点，只有这两个信息都确定了，才能唯一描述一个子串。字符串长度为n，那么i和j都在0到n-1之间，且i必须小于等于j，所以实际用到的只有表格右上三角部分。
这个状态定义是后面所有推导的基础。我见过不少朋友一开始把状态定义成“从0到i的最长回文子串长度”——听起来也是动态规划的思路，但仔细想就会发现它实现不了转移。因为你不知道最长回文子串的结束位置在哪里，就无法从短串推出长串。这其实是一个很好的教训：状态的定义必须能够支持状态转移，如果转移方程写不出来，往往不是转移的问题，而是状态本身定义就出了问题。
2.2 状态转移方程：递推关系怎么来
状态定义好了，接下来就要回答一个关键问题：dp[i][j]能不能由更短的子串结果推出来？
我们来推一下。s[i]到s[j]这一段要想是回文串，必须满足两个条件：第一，s[i]和s[j]这两个字符相等；第二，去掉这两个字符后的中间部分s[i+1]到s[j-1]也必须是回文串。用公式写出来就是：
条件1：s[i] == s[j]
条件2：dp[i+1][j-1] == true
两个条件同时满足，dp[i][j]才等于true。写成代码就是：
if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) { dp[i][j] = true; }这里有个边界情况要想清楚：如果j-i小于等于2，也就是子串长度是1或2或3的时候，中间的dp[i+1][j-1]可能访问到无效的区域。长度为1的子串，i等于j，中间部分就是i+1到j-1，i+1已经大于j-1了，没有意义。长度为2的子串，比如"aa"，只要两个字符相等就是回文串。长度为3的子串，比如"aba"，首尾相等并且中间只有一个字符，单字符一定是回文，所以条件简化成首尾相等就够了。
所以实际操作中，常见的写法是在转移前先判断长度。如果子串长度小于等于2，只要首尾相等就直接判定为回文串，不需要查询中间状态。这样既避免了数组越界，也符合逻辑上的事实。
2.3 为什么遍历方向这么关键
这是动态规划里最容易被忽略、出错率最高的一个环节。dp[i][j]依赖的是dp[i+1][j-1]，注意下标的变化方向：i变大了，j变小了。也就是说，要计算dp[i][j]，你得先知道左侧靠下、右侧靠上那个格子的值。
如果你按常规思路让i从0往后遍历、j从i往后遍历，那么计算dp[0][4]的时候，要查dp[1][3]，此时dp[1][3]其实还没有计算过，程序执行时拿到的就是初始值，结果完全不可靠。很多人栽在这道题上就是这个原因——代码逻辑看起来完全正确，但答案就是不对。
正确的遍历方式是按子串长度从小到大计算。先算所有长度为1的，再算长度为2的，以此类推。这样计算长度为len的子串时，它依赖的长度为len-2的子串必然已经计算好了。
换句话说，外层循环遍历的是长度，内层循环遍历的是起始位置。这个顺序是动态规划的实现核心，也是新手最容易绕晕的地方，后面我会在代码里再详细演示一遍。
3. 完整实现与代码注解
3.1 初始化细节
前面提到单字符一定是回文串，这就是初始化工作。一个n长度的字符串，有n个长度为1的子串，它们的dp[i][i]都应该置为true。初始化这一步不能省，也不难做。
另外还需要记录“当前找到的最长回文子串”的起始位置和长度。初始时，起始位置为0，长度为1。为什么长度初始化为1而不是0？因为任何非空字符串都至少有一个长度为1的回文子串。
实现时我用Java写了一遍，C++和Python的写法在逻辑上是一模一样的，主要是字符串取字符的语法不同。先看代码：
public String longestPalindrome(String s) { int n = s.length(); if (n < 2) { return s; } boolean[][] dp = new boolean[n][n]; int maxLen = 1; int begin = 0; // 初始化：所有长度为1的子串都是回文 for (int i = 0; i < n; i++) { dp[i][i] = true; } // 按子串长度从小到大遍历 for (int len = 2; len <= n; len++) { for (int i = 0; i < n; i++) { int j = i + len - 1; // 如果右端点越界，结束当前长度下的遍历 if (j >= n) { break; } if (s.charAt(i) != s.charAt(j)) { dp[i][j] = false; } else { if (j - i < 3) { // 长度为2或3时，两端相等即为回文 dp[i][j] = true; } else { // 长度大于3时，看中间部分 dp[i][j] = dp[i + 1][j - 1]; } } // 如果当前子串是回文且更长，更新答案 if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1; begin = i; } } } return s.substring(begin, begin + maxLen); }3.2 遍历过程与答案更新
重点说一下中间两层的循环逻辑。外层len表示当前正在计算的子串长度，从2开始，因为长度为1的已经初始化过了。内层i是子串的起始位置，j通过i+len-1计算出来，就是子串的结束位置。
比如字符串"babad"，当len等于3时，依次计算的是"bab"、"aba"、"bad"这三个子串。算"bab"的时候，首尾s[0]和s[2]都是'b'，长度是3且两端相等，直接判定为true。算"aba"同理。而len等于4时计算"baba"，两端s[0]是'b'，s[3]是'a'，不相等，直接false。
这里有个细节值得留意：为什么初始化长度是1，遍历长度从2开始，但答案记录时最长回文子串长度初始值也是1？因为当输入字符串长度为1时，直接返回s本身，根本不会进入遍历循环。当长度为2时，遍历会覆盖所有可能，最长长度至少也是1。这两处保持一致，代码才不会出现“答案最长长度是0”的bug。
更新答案的时机在每次确定dp[i][j]为true之后。因为遍历长度是从短到长的，所以只要发现新的true，它的长度一定不小于之前找到的任何回文子串，更新maxLen和begin即可。
3.3 复杂度分析与边界情况
时间复杂度是O(n²)，两层循环，每层循环的次数都是n量级。空间复杂度同样是O(n²)，因为用了一个二维布尔数组。这两个指标在算法题里算是中规中矩，n在1000到2000级别的字符串都可以轻松跑完。
边界情况我在写代码的时候专门整理了一个清单：
- 空字符串：长度n为0时，直接返回空串。
- 单字符串：比如"a"，直接返回自身。
- 所有字符都相同的字符串，比如"aaaa"：DP表会全部填上true，最长回文子串就是整个串。
- 没有任何回文子串长度大于1的字符串，比如"abcd"：循环里不会更新maxLen，最终返回首个字符。
代码前面已经加了对n小于2的提前返回，所以空串和单字符的情况已经覆盖。至于"abcd"这类情况，初始化maxLen为1就保证了一定有返回值。
读者可以自己手推一遍"babad"的完整DP表，用笔在纸上把每个格子的true/false标记出来，整个过程走下来，比看十遍代码都管用。这也是我想强调的学习方法：动态规划题，第一遍一定要手动模拟一遍小规模用例，把状态转移的流程刻在脑子里。
4. 其他解法对比：DP不是唯一答案
4.1 中心扩展法
动态规划解法虽然好理解，但它并不是这道题的最优解。中心扩展法是另一种非常经典的解法，思路和DP完全不同，但代码更简洁，运行效率也更高。
中心扩展法的核心思想是：回文串一定有一个“中心”。长度为奇数时中心是一个字符，长度为偶数时中心是两个字符中间的位置。从每个中心出发，向两边扩展，只要两边的字符相等，就继续扩展，直到不相等为止，就找到了以这个中心为基准的最长回文子串。
以"babad"为例，从位置1的'a'出发，先比较0号位的'b'和2号位的'b'，相等，继续比较-1和3号位，越界停止，就得到了"bab"，长度3。再从位置2的'b'出发，得到"aba"，长度也是3。最终答案在两者之间任选一个即可。
实现时需要注意奇偶两种情况都要考虑。一个长度为n的字符串，有n个奇数中心和n-1个偶数中心，总共2n-1个中心位置，每个中心扩展的平均成本是O(n)，总体时间复杂度O(n²)。空间复杂度O(1)，比起DP的O(n²)要优秀得多。
我在实际刷题时更推荐初学者先掌握中心扩展法，因为它对回文串“由中心向两边扩展”的几何感觉建立得更直观。DP的二维表虽然也是一种理解方式，但离“回文串到底是什么”有点远。
4.2 马拉车算法了解一下
马拉车算法（Manacher's Algorithm）是这个问题的终极解法，时间复杂度O(n)，是目前已知的最优解。它的核心改进是复用了之前已经计算过的回文半径信息，避免了重复的中心扩展。
具体做法是先把原始字符串每个字符之间插入一个特殊字符（比如'#'），这样所有的回文子串都变成了奇数长度，统一了奇偶两种情况。然后用一个数组记录每个位置的回文半径，利用对称性快速跳过已计算过区域。
马拉车算法虽然优化得很漂亮，但我不太建议初学者在一开始就死磕它。原因有三：第一，笔试和面试中字符串长度一般不会大到O(n²)过不去；第二，马拉车算法的代码细节多，边界条件微妙，很容易写错；第三，它用到的“利用已有信息加速”的思想虽然重要，但放在动态规划学习阶段去理解，会把两个复杂概念混在一起。
4.3 面试和实际场景中怎么选
如果是面试现场，我一般建议先说中心扩展法，思路清晰、代码简洁、面试官好理解，聊透了再提一句“其实还有O(n)的马拉车算法，如果需要我可以讲讲它的思路”。这样既展示了广度，又不至于在基础题上用力过猛。
如果是刷题练习动态规划，那就一定要把DP解法做一遍。这道题的价值不在“解决单道题”，而在于它把DP的完整思考链路走了一遍：状态定义、转移推导、边界条件、遍历顺序。这一步走扎实了，后面做背包问题、编辑距离、正则表达式匹配这类更复杂的DP题时，就有了一套自己的分析框架。
5. 常见问题与排查实录
5.1 数组越界的坑
我见过不少人写完代码一跑，直接报ArrayIndexOutOfBoundsException。问题几乎都出在j的计算上。i从0到n-1，len从2到n，如果不在内层加一道j >= n的判断，i接近n-1时j就会超过n-1，访问数组自然越界。
解决办法有两个：一种是我前面代码里写的，内层循环开头判断j >= n就break；另一种是内层循环的i只遍历到n-len，也就是i < n - len + 1。这两种写法效果相同，看个人习惯。我更喜欢前者，因为在逻辑上它和“枚举所有子串”的直观理解更一致，排查问题时不容易混乱。
5.2 遍历顺序错了怎么办
这是动态规划最常见的问题，表现在结果上就是：要么返回的结果完全不对，要么对小规模用例碰巧是对的、一换测试数据就错。
如果你发现自己写的代码总是不对，第一步先检查遍历顺序。判断方法很简单：看看dp[i][j]依赖的dp[i+1][j-1]在当前遍历顺序下是否已经被计算过。比如i从0往前遍历、j从i往后遍历，那么dp[0][4]依赖的dp[1][3]需要已经存在，但此时循环才刚开始，dp[1][3]尚未被赋值，默认是false，于是"abccba"这类正确结果也会被误判为false。
解决办法就是改成按长度遍历。这也是动态规划里一个通用的准则：依赖的状态必须已经在之前被计算出来。这个规则不是背出来的，而是每次写DP时都要在心里过一遍的。
5.3 子串与子序列不要混为一谈
还有一个高频错误是把“子串”和“子序列”搞混。子串要求连续，子序列只要求相对顺序一致，不需要连续。
例如字符串"babad"，它的回文子序列"babd"里去掉'd'后的"bab"是回文子串，但完整的最长回文子序列是"babab"或者"ababa"（不是"bab"）。最长回文子序列是另一道经典的DP题（LeetCode 516），它的状态定义和转移方程都不一样，如果混在一起做，思路就会全乱。
判断自己做的是哪种题，最简单的方法是看题目里有没有“连续”或者“substring”的明确表述。LeetCode 5的题目明确说了substring，那就是子串。一旦确定是子串，状态定义就必须围绕起点和终点两个维度展开，一维数组基本不够用。
6. 动态规划思维的延伸
6.1 从回文串到01背包
回文串这道题做透了，就可以尝试把DP思维迁移到其他经典问题上，最典型的就是01背包问题。
01背包问题描述很简单：有一堆物品，每个物品有自己的重量和价值，背包容量有限，问怎么放能让总价值最大。它的状态定义是dp[i][j]表示前i个物品放入容量为j的背包能获得的最大价值。转移方程核心是“第i个物品放还是不放”，不放就是dp[i-1][j]，放就是dp[i-1][j-w[i]]+v[i]，取两者较大值。
看出没？它和最长回文子串的思考路径是一样的：先确定状态维度，再推导当前状态和前一状态的关系，最后考虑边界和遍历顺序。不同的只是回文串的状态是布尔值、背包的状态是最大值；回文串的依赖是“斜对角”的dp[i+1][j-1]，背包的依赖是dp[i-1][j-w[i]]，是上一行左边的位置。
所以学DP不要孤立地刷题，每一道经典题都是思维训练的一个环节。回文串练的是二维布尔状态和按长度遍历，背包练的是二维最优值状态和按容量遍历，编辑距离练的是三个方向的转移合并。做多了你会发现，动态规划本质上就是一套固定的思维方法，题目只是换了不同的外衣而已。
6.2 动态规划的学习路线建议
结合我自己刷题的经验，给刚开始学DP的朋友一个建议路线：
第一步，先把一维DP的经典题吃透，比如爬楼梯、最大子序和、打家劫舍。这类题状态定义直观，转移方程简单，可以快速建立DP的基本感觉。
第二步，做二维DP的基础题，最长回文子串就是这一阶段的代表作。重点训练状态定义能力和“从依赖关系推导遍历顺序”的能力。
第三步，接触背包问题、编辑距离这类组合优化题，领悟DP在“决策取舍”场景中的应用。
第四步，再看一些状态压缩、区间DP等进阶内容，逐步提升难度。
每一步都要配合“手推状态表”的动作。我一直认为，动态规划不是靠“看会的”，而是靠“推会的”。你看十篇题解不如自己动手填一次状态表，填过之后你会发现很多原本觉得抽象的术语，突然都有了具体的画面感。
最长回文子串这道题，我前前后后刷过不下五遍，每一次都有新的理解。第一次学会DP解法，第二次理解了遍历顺序为什么重要，第三次对比了中心扩展法，第四次看了马拉车算法，第五次已经可以直接口述完整思路了。这个反复的过程就是算法学习最真实的节奏，希望这篇内容能让你在第一次接触这道题时，就少走一些我当年走过的弯路。
