最长回文子串这道题可以说是动态规划入门路上绕不过去的一道坎。LeetCode第5题看起来就是“给一个字符串找最长的回文子串”但真上手做的时候你会发现它特别适合用来理解动态规划的核心思想状态怎么定义、转移方程怎么推、遍历顺序怎么定。这篇文章我就用刷这道题的完整过程把动态规划这套思路掰开揉碎讲清楚适合刚学DP、或者刷题总是“看答案能懂、自己写就废”的朋友。1. 先搞清楚这道题在干什么1.1 回文串的本质特征回文串这个概念其实很简单就是正着读和倒着读都一样的字符串。比如aba、bb、a都是回文串而ab、abc不是。单字符一定是回文串这一点看起来不起眼但它恰恰是动态规划里最重要的初始化条件后面会反复用到。判断一个字符串是不是回文串最直观的办法是双指针从两头往中间走逐个比对字符。但题目要的不是“判断一个串是不是回文”而是“在一大堆子串里找最长的那个”这就完全不一样了。如果对每个子串都用双指针判断一次以babad为例它的所有子串数量是n(n1)/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[i1]到s[j-1]也必须是回文串。用公式写出来就是条件1s[i] s[j]条件2dp[i1][j-1] true两个条件同时满足dp[i][j]才等于true。写成代码就是if (s.charAt(i) s.charAt(j) dp[i1][j-1]) { dp[i][j] true; }这里有个边界情况要想清楚如果j-i小于等于2也就是子串长度是1或2或3的时候中间的dp[i1][j-1]可能访问到无效的区域。长度为1的子串i等于j中间部分就是i1到j-1i1已经大于j-1了没有意义。长度为2的子串比如aa只要两个字符相等就是回文串。长度为3的子串比如aba首尾相等并且中间只有一个字符单字符一定是回文所以条件简化成首尾相等就够了。所以实际操作中常见的写法是在转移前先判断长度。如果子串长度小于等于2只要首尾相等就直接判定为回文串不需要查询中间状态。这样既避免了数组越界也符合逻辑上的事实。2.3 为什么遍历方向这么关键这是动态规划里最容易被忽略、出错率最高的一个环节。dp[i][j]依赖的是dp[i1][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通过ilen-1计算出来就是子串的结束位置。比如字符串babad当len等于3时依次计算的是bab、aba、bad这三个子串。算bab的时候首尾s[0]和s[2]都是b长度是3且两端相等直接判定为true。算aba同理。而len等于4时计算baba两端s[0]是bs[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直接返回自身。所有字符都相同的字符串比如aaaaDP表会全部填上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 马拉车算法了解一下马拉车算法Manachers Algorithm是这个问题的终极解法时间复杂度O(n)是目前已知的最优解。它的核心改进是复用了之前已经计算过的回文半径信息避免了重复的中心扩展。具体做法是先把原始字符串每个字符之间插入一个特殊字符比如#这样所有的回文子串都变成了奇数长度统一了奇偶两种情况。然后用一个数组记录每个位置的回文半径利用对称性快速跳过已计算过区域。马拉车算法虽然优化得很漂亮但我不太建议初学者在一开始就死磕它。原因有三第一笔试和面试中字符串长度一般不会大到O(n²)过不去第二马拉车算法的代码细节多边界条件微妙很容易写错第三它用到的“利用已有信息加速”的思想虽然重要但放在动态规划学习阶段去理解会把两个复杂概念混在一起。4.3 面试和实际场景中怎么选如果是面试现场我一般建议先说中心扩展法思路清晰、代码简洁、面试官好理解聊透了再提一句“其实还有O(n)的马拉车算法如果需要我可以讲讲它的思路”。这样既展示了广度又不至于在基础题上用力过猛。如果是刷题练习动态规划那就一定要把DP解法做一遍。这道题的价值不在“解决单道题”而在于它把DP的完整思考链路走了一遍状态定义、转移推导、边界条件、遍历顺序。这一步走扎实了后面做背包问题、编辑距离、正则表达式匹配这类更复杂的DP题时就有了一套自己的分析框架。5. 常见问题与排查实录5.1 数组越界的坑我见过不少人写完代码一跑直接报ArrayIndexOutOfBoundsException。问题几乎都出在j的计算上。i从0到n-1len从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[i1][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[i1][j-1]背包的依赖是dp[i-1][j-w[i]]是上一行左边的位置。所以学DP不要孤立地刷题每一道经典题都是思维训练的一个环节。回文串练的是二维布尔状态和按长度遍历背包练的是二维最优值状态和按容量遍历编辑距离练的是三个方向的转移合并。做多了你会发现动态规划本质上就是一套固定的思维方法题目只是换了不同的外衣而已。6.2 动态规划的学习路线建议结合我自己刷题的经验给刚开始学DP的朋友一个建议路线第一步先把一维DP的经典题吃透比如爬楼梯、最大子序和、打家劫舍。这类题状态定义直观转移方程简单可以快速建立DP的基本感觉。第二步做二维DP的基础题最长回文子串就是这一阶段的代表作。重点训练状态定义能力和“从依赖关系推导遍历顺序”的能力。第三步接触背包问题、编辑距离这类组合优化题领悟DP在“决策取舍”场景中的应用。第四步再看一些状态压缩、区间DP等进阶内容逐步提升难度。每一步都要配合“手推状态表”的动作。我一直认为动态规划不是靠“看会的”而是靠“推会的”。你看十篇题解不如自己动手填一次状态表填过之后你会发现很多原本觉得抽象的术语突然都有了具体的画面感。最长回文子串这道题我前前后后刷过不下五遍每一次都有新的理解。第一次学会DP解法第二次理解了遍历顺序为什么重要第三次对比了中心扩展法第四次看了马拉车算法第五次已经可以直接口述完整思路了。这个反复的过程就是算法学习最真实的节奏希望这篇内容能让你在第一次接触这道题时就少走一些我当年走过的弯路。