1. 先把题读懂最长回文子串到底在求什么1.1 题目背景与核心概念接触动态规划最长回文子串基本是绕不开的一道题。它在LeetCode上是第5题看似只是一个字符串处理问题实际背后牵出的是整个动态规划领域的核心方法论。很多人在刷这道题之前对动态规划的印象停留在“背包九讲”“状态转移方程”这类抽象的名词上真正自己推一遍这道题才算把“状态”“转移”“边界”这三个词落地了。先明确题目本身给定一个字符串 s要求返回 s 中最长的回文子串。回文的意思是正着读和反着读结果一样比如 aba、aa、cbbc都是回文。这里有个很容易混淆的地方——题目要的是“子串”不是“子序列”。子串要求字符在原字符串中必须是连续的而子序列只要求保持相对顺序可以在中间跳过字符。这个区别直接决定了状态定义和转移方程的写法后面会反复提到。举个例子字符串 babad 里bab 是回文子串aba 也是回文子串长度都是 3所以返回任意一个都算正确。但如果是找最长回文子序列结果就会是 babab 或者 badab 这类长度为 5 的结果因为子序列允许跳字符。很多初学者在这个地方翻车代码写完之后发现结果跟预期不一致回头排查才发现是把子串和子序列搞混了。还有一个隐蔽的细节题目里说的“子串”默认指的是原始字符串的连续一段也就是一个区间 [i, j]其中 0 i j n。所以这个问题在数学上可以描述成在所有满足 s[i..j] 是回文串的区间中找到 j - i 1 最大的那一个。一旦把它转化成区间问题动态规划的思路就自然浮现了——因为区间关系天然具有嵌套结构。1.2 为什么这题会用到动态规划我第一次做这题时第一反应是暴力枚举。穷举所有起点 i 和终点 j判断每个子串是不是回文记录最长的那个。思路没有任何问题问题是复杂度枚举所有子串是 O(n^2)判断一个子串是否为回文需要 O(n)总复杂度 O(n^3)。当字符串长度到 1000 以上三层循环直接就卡死了LeetCode 上的测试用例可不会给你留面子。那有没有办法把“判断回文”这一步的时间降下来这时候需要观察回文的递归性质一个子串 s[i..j] 是回文当且仅当 s[i] s[j]并且 s[i1..j-1] 也是回文。这个性质看起来平平无奇但它揭示了一个重要事实——大区间的回文性依赖于更小区间的回文性。也就是说如果我们已经知道所有长度为 len - 2 的子串是否为回文那么长度为 len 的子串是否是回文只需要一次字符比较就能得到。这种“大问题依赖更小同类问题”的结构就是动态规划最典型的信号。它不是靠什么高深莫测的灵感而是自然地从问题本身的递归性质里生长出来的。回到题目上我们可以用一个二维数组 dp[i][j] 记录子串 s[i..j] 是否为回文这样“判断一个子串是否为回文”的时间就从 O(n) 降到了 O(1) —— 直接查表。很多教程喜欢一开始就甩出状态转移方程读者对着一行公式看半天也不知道它是怎么来的。实际上你只要自己动手写几组例子就能推出来拿 aba 来说首尾都是 a去掉首尾剩一个 b而 b 显然是个回文所以 aba 是回文。拿 abc 来说首尾 a 和 c 不相等直接判定为不是回文根本没必再看内部。这个逻辑落到代码里就是两条分支。2. 动态规划建模状态怎么定、方程怎么来2.1 状态定义dp[i][j] 表示 s[i..j] 是否为回文动态规划的第一步永远是定义状态。状态定义的好坏直接决定后续所有代码的复杂度和可读性。对于最长回文子串最自然的做法就是定义一个二维布尔数组dp[i][j] true 表示字符串 s 从下标 i 到 j 的这一段是回文串false 则表示不是。其中 i 和 j 满足 0 i j n。这里用二维数组而不是一维数组是因为回文性同时依赖左边界和右边界两个维度。有读者可能会问能不能用 dp[i] 表示以 i 结尾的最长回文子串长度从直觉上好像也可以但实际推导起来会很别扭——因为当你尝试扩展 dp[i] 时你需要知道 s[i - len] 和 s[i 1] 的关系而“回文串左边界”这个信息在单维状态里根本存不下来。区间类问题本身就是二维的强行压缩成一维只会让转移逻辑变得绕来绕去。状态定义确定之后还需要明确边界初始值。对于所有 idp[i][i] true因为单个字符一定是回文。对于所有 idp[i][i1] (s[i] s[i1])因为两个字符的回文性只取决于它们是否相等。这两个初始条件是为了给长度为 1 和长度为 2 的子串打好底子后续长度为 3、4、5 乃至更长的子串都是在它们的基础上逐层扩展出来的。2.2 状态转移方程推导有了状态定义和初始条件接下来就是整个动态规划中最核心的一步推导状态转移方程。根据回文的递归性质我们可以写出dp[i][j] (s[i] s[j]) dp[i1][j-1]这个方程的意思是s[i..j] 是回文需要同时满足两个条件。第一左右两端的字符相等也就是 s[i] s[j]第二去掉左右两端之后内部的子串 s[i1..j-1] 也是回文。这个逻辑非常直观可以用剥洋葱来理解判断一个洋葱是不是完好的先看最外层的皮是否完整再剥掉这层皮继续看里面的洋葱是不是完好的。但这里有一个细节需要处理当子串长度小于等于 3 时去掉两端之后内部可能只剩 0 个或 1 个字符。比如 aa去掉两端之后是空串空串当然算是回文再比如 aba去掉两端之后是 b单个字符也是回文。但是我们的 dp 数组定义里i1 可能大于 j-1也就是子串不存在或者是一个“没有意义”的区间。为了避免数组越界也为了让逻辑更清晰通常会把转移方程改写成带长度判断的形式dp[i][j] (s[i] s[j]) (j - i 3 || dp[i1][j-1])这里的 j - i 3 表示子串长度不超过 3也就是长度为 1、2、3 的情况。长度 1 和 2 已经被初始条件覆盖了长度 3 的情况下只要首尾相等中间的那个字符无论是什么整个串必然是回文。举个例子aba 首尾都是 a中间是 b不管 b 是什么都改变不了 aba 是回文这个事实。用 j - i 3 这个条件可以直接跳过 dp[i1][j-1] 的查询既避免越界又简化逻辑。伪代码写出来就是这个样子if s[i] s[j]: if j - i 3: dp[i][j] true else: dp[i][j] dp[i1][j-1] else: dp[i][j] false这段伪代码直接翻译成任意编程语言都很容易。很多初学者照着这个逻辑写完之后会发现结果不对排查半天发现是遍历顺序出了问题。这就要说到动态规划实现里的一个关键细节——遍历顺序。2.3 遍历顺序为什么是关键动态规划的实现本质上是在填一张二维表格。表格填的顺序必须保证计算某个格子时它所依赖的格子已经被计算过了。对于最长回文子串dp[i][j] 依赖的是 dp[i1][j-1]也就是左下方偏左的格子。如果用横轴表示 j纵轴表示 i那么 dp[i1][j-1] 位于 dp[i][j] 的“左下角”位置。如果我们按照常规的 i 从小到大、j 从小到大的顺序遍历会发生什么当计算 dp[i][j] 时dp[i1][j-1] 还没有被计算出来因为它对应的 i1 更大在内层循环中还没轮到。这就像盖房子时想先盖第二层但第一层还没打地基。正确的遍历方式有两种。第一种是按子串长度从短到长遍历先计算长度为 1 的子串再计算长度为 2 的子串依次类推。这样当计算长度为 len 的子串时它依赖的长度为 len - 2 的子串一定已经被计算过了。第二种方式是调整 i 和 j 的遍历方向外层循环 i 从 n-1 往 0 递减内层循环 j 从 i 往 n-1 递增。这样计算 dp[i][j] 时dp[i1][j-1] 对应着更小的 i而由于外层循环是从大到小它已经被填充过了。这两种方式在实现上略有差异但本质上都是为了保证依赖关系被满足。我个人更推荐按长度遍历因为它的思路更贴近“子问题从小到大的求解”这一动态规划核心思想而且代码可读性更好。但不管理解哪种你都必须明白一点动态规划的遍历顺序不是随便写的它是由状态转移方程中依赖的方向决定的。3. 三种实现方式对比从暴力到动态规划到中心扩展3.1 暴力枚举思路简单但复杂度高在学习动态规划之前很多人会先尝试暴力解法。暴力的思路很直接枚举所有可能的子串开头 i 和结尾 j然后写一个辅助函数判断 s[i..j] 是否是回文。如果当前子串是回文并且长度大于已记录的最大长度就更新答案。判断回文的函数本身不难写两个指针从两端向中间移动逐个比较字符只要有一次不相等就直接返回 false。整个算法的代码大概长这样def is_palindrome(s, left, right): while left right: if s[left] ! s[right]: return False left 1 right - 1 return True def longest_palindrome_brutal(s): n len(s) max_len 0 start 0 for i in range(n): for j in range(i, n): if is_palindrome(s, i, j) and j - i 1 max_len: max_len j - i 1 start i return s[start:start max_len]这个解法的时间复杂度是 O(n^3)空间复杂度是 O(1)。它的价值在于思路简单容易写对适合用来验证题目理解是否正确。但一旦字符串长度上升到几千运行时间就会呈指数级地让人难以忍受。我在实际面试中见过不少候选人能写出暴力解但当被问到“能不能优化到 O(n^2)”时就卡住了。暴力解不是终点而是认识问题的起点。3.2 动态规划常规解法中的正主动态规划解法的代码实现并不复杂关键是要把前面讲的状态定义、转移方程和遍历顺序落实成代码。下面这份 Python 实现是 LeetCode 上最常见的写法之一def longest_palindrome_dp(s): n len(s) if n 2: return s dp [[False] * n for _ in range(n)] start 0 max_len 1 # 初始化单个字符一定是回文 for i in range(n): dp[i][i] True # 按子串长度从小到大遍历 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 if s[i] s[j]: if length 2: dp[i][j] True else: dp[i][j] dp[i 1][j - 1] if dp[i][j] and length max_len: max_len length start i return s[start:start max_len]这份代码里有几个细节值得特别注意。第一如果字符串为空或者只有一个字符直接返回本身这是边界条件。第二初始化 dp[i][i] True对应长度为 1 的子串。第三外层循环对子串长度进行遍历内层循环枚举左起点 i右端点 j 通过 i length - 1 计算得到。第四当 length 2 时只需要判断两个字符是否相等不需要查询内部子串。在更新答案时我没有记录右端点而是只记录 start 和 max_len最后用切片返回。这样做的好处是代码更简洁避免在循环里同时维护多个变量时出现差一错误。实际运行中这个算法的时间复杂度是 O(n^2)空间复杂度是 O(n^2)。对于 LeetCode 的测试数据规模来说已经足够应对。3.3 中心扩展法空间 O(1) 的替代方案在面试或实际项目中动态规划虽然直观但需要 O(n^2) 的额外空间这并不算最优。解决最长回文子串还有一个常见思路——中心扩展法它的空间复杂度可以降到 O(1)。中心扩展法的核心思想是回文串是对称的所以可以从每个“中心”向两边扩展判断能扩展到多长。这里的关键是“中心”有两种情况一种是奇数长度的回文中心是一个字符比如 aba 的中心是 b另一种是偶数长度的回文中心是两个字符之间比如 abba 的中心在 b 和 b 之间。具体做法是枚举每个可能的中心然后同时向左右扩展只要左右两端的字符相等就继续扩展直到不相等或者越界为止。每次扩展之后记录当前回文串的长度和起点。def expand_around_center(s, left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return left 1, right - 1 def longest_palindrome_center(s): n len(s) start 0 max_len 1 for i in range(n): # 奇数长度回文中心为 i l1, r1 expand_around_center(s, i, i) if r1 - l1 1 max_len: max_len r1 - l1 1 start l1 # 偶数长度回文中心在 i 和 i1 之间 l2, r2 expand_around_center(s, i, i 1) if r2 - l2 1 max_len: max_len r2 - l2 1 start l2 return s[start:start max_len]这个算法的时间复杂度同样是 O(n^2)但空间复杂度为 O(1)。在实际面试中如果要求“写一个解法”动态规划和中心扩展都可以如果要求“优化空间复杂度”那就应该写中心扩展。顺便提一句最长回文子串还有一个更高级的 Manacher 算法可以把时间优化到 O(n)但它利用了回文对称性的本质属于进阶内容这里先不展开。3.4 三种解法对比怎么选解法时间复杂度空间复杂度核心思路适用场景暴力枚举O(n^3)O(1)枚举所有子串并逐一判断仅用于理解题意n 很小动态规划O(n^2)O(n^2)区间状态转移空间换时间学习动态规划思想n 在几千以内中心扩展O(n^2)O(1)回文对称性从中心向两边生长面试手写空间受限的项目场景从学习价值来看动态规划解法是最值得深入研究的。因为状态定义、转移方程、遍历顺序这三件事是所有区间类动态规划问题的通用框架。中心扩展法虽然更省空间但它对动态规划思维的训练帮助不大。所以我的建议是初学者先把动态规划解法吃透再去学习中心扩展两者互相印证之后对回文问题的理解会更立体。4. 实操踩坑边界条件与常见错误排查4.1 边界条件全梳理代码能跑通和能跑对是两个层面的问题。最长回文子串的边界条件非常容易出错我把常见的几种情况列一下你可以对照着检查自己的代码第一空字符串。输入为 时最长的回文子串是 长度是 0。很多人的代码在n 2的判断里直接返回 s这没问题但要注意 Python 里 n 为 0 时 s[0:0] 返回的是空字符串不会报错。第二单个字符。输入为 a 时最长回文子串就是 a 本身。这个在初始化 dp[i][i] True 时已经覆盖。第三所有字符都不相同。比如 abcde此时最长回文子串可以是任意一个字符长度是 1。动态规划代码中的 max_len 初始值必须设为 1否则可能返回空字符串。第四所有字符都相同。比如 aaaa最长回文子串是 aaaa 全长。这种用例是用来测试遍历顺序是否正确的绝佳测试用例因为它的所有子串都是回文只要遍历顺序错了答案就会出错。第五字符串长度恰好为 2 的情况。比如 aa 和 ab前者整个是回文后者只能取单个字符。ab 这类用例用来检查 length 2 的特殊分支是否处理正确。4.2 常见错误实录我自己踩过的坑这道题我刷了很多遍也帮别人 review 过代码这里整理几个反复出现的错误。第一个错误是忘记初始化 dp[i][i] True。如果跳过初始化当 length 3 时dp[i1][j-1] 可能引用了未初始化的 False导致最终结果漏掉很多回文串比如 aba 就会被误判为不是回文。这个错误很隐蔽因为结果不是直接报错而是返回了一个错误长度的子串。第二个错误是遍历顺序写反。有些人习惯性地把外层循环写成 i 从 0 到 n内层循环写成 j 从 0 到 n结果整个表格的依赖关系全乱了。这种错误最常见的表现是输入 aaaa 时只返回 aa而不是 aaaa。如果你遇到这种情况优先检查遍历顺序。第三个错误是在更新答案时只记录了长度没有记录起点导致最后不知道要从哪里切片。在动态规划表格里你完全可以在循环中顺便记录start变量关键是在每个dp[i][j]为 true 时都用j - i 1和当前max_len比较如果更大就更新start和max_len。第四个错误是想当然地尝试用一维滚动数组优化。最长回文子串的 dp[i][j] 依赖的是 dp[i1][j-1]也就是“下一行的前一个元素”。如果要压缩空间需要保留上一行的完整信息而且更新的方向必须是从左向右。这个优化思路是可以写出来的但远不如中心扩展法直接。新手阶段建议老老实实用二维数组先把逻辑理清楚再考虑空间优化。4.3 测试用例设计技巧写算法题设计一批有针对性的测试用例比盲目提交代码更能提升通过率。我常用的测试用例包括babad经典用例存在多个同长度的结果验证答案是否正确cbbd偶数长度回文 bb专门检验偶数分支a单字符边界ac无回文子串长度1的除外检验边界初始化aaaa全同字符检验遍历顺序abcba以中心为对称轴的奇数长度回文abacdfgdcaba其中包含 aba 和 abacdfgdcaba 不是回文但有回文前缀/后缀检验区间判断是否正确用这些用例跑一遍你的代码如果都能通过基本可以放心提交了。如果某个用例失败不要急着改代码先手动模拟一遍 dp 表格看看到底是哪一格的状态算错了这样排查起来更快。5. 从回文子串到 01 背包读懂动态规划的通用套路5.1 动态规划三要素状态、转移、边界很多人刷动态规划题时总觉得自己在背题换个题目就不会了。这是因为没有真正理解动态规划的通用套路。其实不管是最长回文子串还是热词里提到的 01 背包问题甚至是最长递增子序列、编辑距离它们都逃不出三件事状态定义、状态转移方程、边界条件与初始化。状态定义解决的是“我要求的是什么用什么样的数据结构来存储子问题的答案”。在最长回文子串里状态是 dp[i][j] 表示子串是否为回文在 01 背包里状态是 dp[i][w] 表示前 i 件物品在容量为 w 的背包里能够获得的最大价值。状态转移方程解决的是“大问题怎样由小问题推导出来”。在回文子串里是首尾字符相等且内部子串为回文在 01 背包里是“不选第 i 件物品”和“选第 i 件物品”两种决策取最大值。边界条件解决的是“最小子问题的答案是什么”。在回文子串里是单个字符 dp[i][i] True在 01 背包里是 dp[0][w] 0因为没有物品可选时价值为 0。这三者缺一不可。状态定义错了转移方程一定错转移方程对但边界没初始化结果还是错。所以你在学习任何一道动态规划题时建议自问三个问题这个状态定义合理吗转移方程是怎么推导出来的最小的子问题怎么处理能把这三个问题回答清楚基本就掌握了这道题。5.2 01 背包的状态模型选与不选01 背包问题是一个几乎每本算法书都会收录的经典动态规划题目。问题描述是这样的有 n 件物品和一个容量为 W 的背包每件物品有自己的重量 w[i] 和价值 v[i]问怎样选择物品装入背包能让背包中的总价值最大而且每件物品最多只能选一次。它的状态定义是 dp[i][j] 表示从前 i 件物品中选择一些放入容量为 j 的背包中能获得的最大价值。转移方程有两种情况不选第 i 件物品那么 dp[i][j] dp[i-1][j]选第 i 件物品前提是 j w[i]那么 dp[i][j] dp[i-1][j-w[i]] v[i]。取这两个中的较大值即可。对照回文子串的转移方程你会发现本质上是同一件事一个问题是“同一区间的回文性依赖内部区间的回文性”另一个问题是“当前物品选不选依赖前 i-1 件物品的选择结果”。它们都是通过分治的思想把复杂的原问题拆分成规模更小的子问题再通过查表的方式避免重复计算。区别在于状态依赖的方向。回文子串是“区间右下角依赖区间左下角”方向是斜向的所以遍历顺序要按长度从小到大01 背包是“当前行依赖上一行”方向是纵向的所以遍历顺序是外层物品、内层容量。理解了这个依赖方向你就知道为什么有些动态规划可以滚动数组优化有些不能。5.3 怎么判断一道题能不能用动态规划实际做题的经验多了之后你会发现动态规划适用的题目通常有两个典型特征。第一个特征是最优子结构原问题的最优解包含子问题的最优解。在最长回文子串中如果 s[i..j] 是回文那么 s[i1..j-1] 也必须是回文这就是一种最优子结构。在 01 背包中如果前 i 件物品在容量 j 下的最优解选择了第 i 件物品那么去掉它之后的前 i-1 件物品必须在容量 j-w[i] 下达到最优否则可以替换成更优的解。如果一个题目里子问题的最优解不能被复用那动态规划就不太适用。第二个特征是重叠子问题。在暴力求解过程中同一个子问题会被反复计算很多次。比如判断 aba 和 ababa 是否为回文时内部都会判断 b 是否为回文。如果每次都用递归重新计算重复工作量非常大。动态规划通过用一个表格把子问题的答案存起来每次需要时直接查表这就是“以空间换时间”的本质。这两个特征缺一不可。有些题目有最优子结构但子问题不重叠比如归并排序那就适合用分治而不是动态规划有些题目子问题重叠但没有最优子结构比如一些贪心问题那就不能强制用动态规划。5.4 刷题建议与学习路径如果你是刚接触动态规划我给的建议是不要一上来就刷一堆难题先把几个最经典的问题吃透。最长回文子串是一个非常好的入门题因为它状态定义直观转移方程简单边界也少而且和中心扩展法形成了互补。我自己的学习路径是这样的先做最长回文子串把二维 DP 的表格法练熟然后做 01 背包理解一维滚动数组的优化技巧再做最长递增子序列和编辑距离。这四个题目覆盖了动态规划最常见的几种模式区间 DP、线性 DP、双序列 DP。熟练掌握这四类之后再去刷 LeetCode 上 tag 为动态规划的题目会顺畅很多。关于刷题频率我的体会是动态规划需要“温故而知新”。同一道题隔两三个月再刷一遍你可能会发现以前没注意到的细节。我至今还会偶尔回来重新做一遍最长回文子串每次都会有不同的理解深度。6. 再聊聊我第一次做这道题时的经历我第一次接触最长回文子串是在一次面试前的集中刷题阶段。当时我对动态规划的理解基本停留在“背包问题”上看到这道题完全不知道从哪里下手暴力解提交之后果然超时。后来我去看题解看了三遍状态转移方程才看懂为什么 dp[i][j] 要写成那样又调试了大半天才搞明白遍历顺序的问题。现在回头看这道题把动态规划的关键要素都串起来了状态定义要有意义转移方程要靠推导而不靠死记遍历顺序由依赖关系决定边界条件要在写代码之前就想清楚。给一个还没有入门的读者说句实在话如果你能在一张草稿纸上手工模拟一个长度为 5 的字符串的 dp 表格填表过程每填一格都能说出为什么是这个值那这道题你基本就掌握了。一个小技巧是把 dp 表格画出来用行表示 i列表示 j然后把对角线先涂成 true再按照长度从短到长的顺序依次填充。你会发现表格是“沿着对角线一层一层往右上角填”的这种感觉比单纯读代码要直观得多。我每次教别人动态规划都会让他们先画表格再写代码效果比直接讲公式好太多。 深入浅出最长回文子串：动态规划与状态转移实战
1. 先把题读懂最长回文子串到底在求什么1.1 题目背景与核心概念接触动态规划最长回文子串基本是绕不开的一道题。它在LeetCode上是第5题看似只是一个字符串处理问题实际背后牵出的是整个动态规划领域的核心方法论。很多人在刷这道题之前对动态规划的印象停留在“背包九讲”“状态转移方程”这类抽象的名词上真正自己推一遍这道题才算把“状态”“转移”“边界”这三个词落地了。先明确题目本身给定一个字符串 s要求返回 s 中最长的回文子串。回文的意思是正着读和反着读结果一样比如 aba、aa、cbbc都是回文。这里有个很容易混淆的地方——题目要的是“子串”不是“子序列”。子串要求字符在原字符串中必须是连续的而子序列只要求保持相对顺序可以在中间跳过字符。这个区别直接决定了状态定义和转移方程的写法后面会反复提到。举个例子字符串 babad 里bab 是回文子串aba 也是回文子串长度都是 3所以返回任意一个都算正确。但如果是找最长回文子序列结果就会是 babab 或者 badab 这类长度为 5 的结果因为子序列允许跳字符。很多初学者在这个地方翻车代码写完之后发现结果跟预期不一致回头排查才发现是把子串和子序列搞混了。还有一个隐蔽的细节题目里说的“子串”默认指的是原始字符串的连续一段也就是一个区间 [i, j]其中 0 i j n。所以这个问题在数学上可以描述成在所有满足 s[i..j] 是回文串的区间中找到 j - i 1 最大的那一个。一旦把它转化成区间问题动态规划的思路就自然浮现了——因为区间关系天然具有嵌套结构。1.2 为什么这题会用到动态规划我第一次做这题时第一反应是暴力枚举。穷举所有起点 i 和终点 j判断每个子串是不是回文记录最长的那个。思路没有任何问题问题是复杂度枚举所有子串是 O(n^2)判断一个子串是否为回文需要 O(n)总复杂度 O(n^3)。当字符串长度到 1000 以上三层循环直接就卡死了LeetCode 上的测试用例可不会给你留面子。那有没有办法把“判断回文”这一步的时间降下来这时候需要观察回文的递归性质一个子串 s[i..j] 是回文当且仅当 s[i] s[j]并且 s[i1..j-1] 也是回文。这个性质看起来平平无奇但它揭示了一个重要事实——大区间的回文性依赖于更小区间的回文性。也就是说如果我们已经知道所有长度为 len - 2 的子串是否为回文那么长度为 len 的子串是否是回文只需要一次字符比较就能得到。这种“大问题依赖更小同类问题”的结构就是动态规划最典型的信号。它不是靠什么高深莫测的灵感而是自然地从问题本身的递归性质里生长出来的。回到题目上我们可以用一个二维数组 dp[i][j] 记录子串 s[i..j] 是否为回文这样“判断一个子串是否为回文”的时间就从 O(n) 降到了 O(1) —— 直接查表。很多教程喜欢一开始就甩出状态转移方程读者对着一行公式看半天也不知道它是怎么来的。实际上你只要自己动手写几组例子就能推出来拿 aba 来说首尾都是 a去掉首尾剩一个 b而 b 显然是个回文所以 aba 是回文。拿 abc 来说首尾 a 和 c 不相等直接判定为不是回文根本没必再看内部。这个逻辑落到代码里就是两条分支。2. 动态规划建模状态怎么定、方程怎么来2.1 状态定义dp[i][j] 表示 s[i..j] 是否为回文动态规划的第一步永远是定义状态。状态定义的好坏直接决定后续所有代码的复杂度和可读性。对于最长回文子串最自然的做法就是定义一个二维布尔数组dp[i][j] true 表示字符串 s 从下标 i 到 j 的这一段是回文串false 则表示不是。其中 i 和 j 满足 0 i j n。这里用二维数组而不是一维数组是因为回文性同时依赖左边界和右边界两个维度。有读者可能会问能不能用 dp[i] 表示以 i 结尾的最长回文子串长度从直觉上好像也可以但实际推导起来会很别扭——因为当你尝试扩展 dp[i] 时你需要知道 s[i - len] 和 s[i 1] 的关系而“回文串左边界”这个信息在单维状态里根本存不下来。区间类问题本身就是二维的强行压缩成一维只会让转移逻辑变得绕来绕去。状态定义确定之后还需要明确边界初始值。对于所有 idp[i][i] true因为单个字符一定是回文。对于所有 idp[i][i1] (s[i] s[i1])因为两个字符的回文性只取决于它们是否相等。这两个初始条件是为了给长度为 1 和长度为 2 的子串打好底子后续长度为 3、4、5 乃至更长的子串都是在它们的基础上逐层扩展出来的。2.2 状态转移方程推导有了状态定义和初始条件接下来就是整个动态规划中最核心的一步推导状态转移方程。根据回文的递归性质我们可以写出dp[i][j] (s[i] s[j]) dp[i1][j-1]这个方程的意思是s[i..j] 是回文需要同时满足两个条件。第一左右两端的字符相等也就是 s[i] s[j]第二去掉左右两端之后内部的子串 s[i1..j-1] 也是回文。这个逻辑非常直观可以用剥洋葱来理解判断一个洋葱是不是完好的先看最外层的皮是否完整再剥掉这层皮继续看里面的洋葱是不是完好的。但这里有一个细节需要处理当子串长度小于等于 3 时去掉两端之后内部可能只剩 0 个或 1 个字符。比如 aa去掉两端之后是空串空串当然算是回文再比如 aba去掉两端之后是 b单个字符也是回文。但是我们的 dp 数组定义里i1 可能大于 j-1也就是子串不存在或者是一个“没有意义”的区间。为了避免数组越界也为了让逻辑更清晰通常会把转移方程改写成带长度判断的形式dp[i][j] (s[i] s[j]) (j - i 3 || dp[i1][j-1])这里的 j - i 3 表示子串长度不超过 3也就是长度为 1、2、3 的情况。长度 1 和 2 已经被初始条件覆盖了长度 3 的情况下只要首尾相等中间的那个字符无论是什么整个串必然是回文。举个例子aba 首尾都是 a中间是 b不管 b 是什么都改变不了 aba 是回文这个事实。用 j - i 3 这个条件可以直接跳过 dp[i1][j-1] 的查询既避免越界又简化逻辑。伪代码写出来就是这个样子if s[i] s[j]: if j - i 3: dp[i][j] true else: dp[i][j] dp[i1][j-1] else: dp[i][j] false这段伪代码直接翻译成任意编程语言都很容易。很多初学者照着这个逻辑写完之后会发现结果不对排查半天发现是遍历顺序出了问题。这就要说到动态规划实现里的一个关键细节——遍历顺序。2.3 遍历顺序为什么是关键动态规划的实现本质上是在填一张二维表格。表格填的顺序必须保证计算某个格子时它所依赖的格子已经被计算过了。对于最长回文子串dp[i][j] 依赖的是 dp[i1][j-1]也就是左下方偏左的格子。如果用横轴表示 j纵轴表示 i那么 dp[i1][j-1] 位于 dp[i][j] 的“左下角”位置。如果我们按照常规的 i 从小到大、j 从小到大的顺序遍历会发生什么当计算 dp[i][j] 时dp[i1][j-1] 还没有被计算出来因为它对应的 i1 更大在内层循环中还没轮到。这就像盖房子时想先盖第二层但第一层还没打地基。正确的遍历方式有两种。第一种是按子串长度从短到长遍历先计算长度为 1 的子串再计算长度为 2 的子串依次类推。这样当计算长度为 len 的子串时它依赖的长度为 len - 2 的子串一定已经被计算过了。第二种方式是调整 i 和 j 的遍历方向外层循环 i 从 n-1 往 0 递减内层循环 j 从 i 往 n-1 递增。这样计算 dp[i][j] 时dp[i1][j-1] 对应着更小的 i而由于外层循环是从大到小它已经被填充过了。这两种方式在实现上略有差异但本质上都是为了保证依赖关系被满足。我个人更推荐按长度遍历因为它的思路更贴近“子问题从小到大的求解”这一动态规划核心思想而且代码可读性更好。但不管理解哪种你都必须明白一点动态规划的遍历顺序不是随便写的它是由状态转移方程中依赖的方向决定的。3. 三种实现方式对比从暴力到动态规划到中心扩展3.1 暴力枚举思路简单但复杂度高在学习动态规划之前很多人会先尝试暴力解法。暴力的思路很直接枚举所有可能的子串开头 i 和结尾 j然后写一个辅助函数判断 s[i..j] 是否是回文。如果当前子串是回文并且长度大于已记录的最大长度就更新答案。判断回文的函数本身不难写两个指针从两端向中间移动逐个比较字符只要有一次不相等就直接返回 false。整个算法的代码大概长这样def is_palindrome(s, left, right): while left right: if s[left] ! s[right]: return False left 1 right - 1 return True def longest_palindrome_brutal(s): n len(s) max_len 0 start 0 for i in range(n): for j in range(i, n): if is_palindrome(s, i, j) and j - i 1 max_len: max_len j - i 1 start i return s[start:start max_len]这个解法的时间复杂度是 O(n^3)空间复杂度是 O(1)。它的价值在于思路简单容易写对适合用来验证题目理解是否正确。但一旦字符串长度上升到几千运行时间就会呈指数级地让人难以忍受。我在实际面试中见过不少候选人能写出暴力解但当被问到“能不能优化到 O(n^2)”时就卡住了。暴力解不是终点而是认识问题的起点。3.2 动态规划常规解法中的正主动态规划解法的代码实现并不复杂关键是要把前面讲的状态定义、转移方程和遍历顺序落实成代码。下面这份 Python 实现是 LeetCode 上最常见的写法之一def longest_palindrome_dp(s): n len(s) if n 2: return s dp [[False] * n for _ in range(n)] start 0 max_len 1 # 初始化单个字符一定是回文 for i in range(n): dp[i][i] True # 按子串长度从小到大遍历 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 if s[i] s[j]: if length 2: dp[i][j] True else: dp[i][j] dp[i 1][j - 1] if dp[i][j] and length max_len: max_len length start i return s[start:start max_len]这份代码里有几个细节值得特别注意。第一如果字符串为空或者只有一个字符直接返回本身这是边界条件。第二初始化 dp[i][i] True对应长度为 1 的子串。第三外层循环对子串长度进行遍历内层循环枚举左起点 i右端点 j 通过 i length - 1 计算得到。第四当 length 2 时只需要判断两个字符是否相等不需要查询内部子串。在更新答案时我没有记录右端点而是只记录 start 和 max_len最后用切片返回。这样做的好处是代码更简洁避免在循环里同时维护多个变量时出现差一错误。实际运行中这个算法的时间复杂度是 O(n^2)空间复杂度是 O(n^2)。对于 LeetCode 的测试数据规模来说已经足够应对。3.3 中心扩展法空间 O(1) 的替代方案在面试或实际项目中动态规划虽然直观但需要 O(n^2) 的额外空间这并不算最优。解决最长回文子串还有一个常见思路——中心扩展法它的空间复杂度可以降到 O(1)。中心扩展法的核心思想是回文串是对称的所以可以从每个“中心”向两边扩展判断能扩展到多长。这里的关键是“中心”有两种情况一种是奇数长度的回文中心是一个字符比如 aba 的中心是 b另一种是偶数长度的回文中心是两个字符之间比如 abba 的中心在 b 和 b 之间。具体做法是枚举每个可能的中心然后同时向左右扩展只要左右两端的字符相等就继续扩展直到不相等或者越界为止。每次扩展之后记录当前回文串的长度和起点。def expand_around_center(s, left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return left 1, right - 1 def longest_palindrome_center(s): n len(s) start 0 max_len 1 for i in range(n): # 奇数长度回文中心为 i l1, r1 expand_around_center(s, i, i) if r1 - l1 1 max_len: max_len r1 - l1 1 start l1 # 偶数长度回文中心在 i 和 i1 之间 l2, r2 expand_around_center(s, i, i 1) if r2 - l2 1 max_len: max_len r2 - l2 1 start l2 return s[start:start max_len]这个算法的时间复杂度同样是 O(n^2)但空间复杂度为 O(1)。在实际面试中如果要求“写一个解法”动态规划和中心扩展都可以如果要求“优化空间复杂度”那就应该写中心扩展。顺便提一句最长回文子串还有一个更高级的 Manacher 算法可以把时间优化到 O(n)但它利用了回文对称性的本质属于进阶内容这里先不展开。3.4 三种解法对比怎么选解法时间复杂度空间复杂度核心思路适用场景暴力枚举O(n^3)O(1)枚举所有子串并逐一判断仅用于理解题意n 很小动态规划O(n^2)O(n^2)区间状态转移空间换时间学习动态规划思想n 在几千以内中心扩展O(n^2)O(1)回文对称性从中心向两边生长面试手写空间受限的项目场景从学习价值来看动态规划解法是最值得深入研究的。因为状态定义、转移方程、遍历顺序这三件事是所有区间类动态规划问题的通用框架。中心扩展法虽然更省空间但它对动态规划思维的训练帮助不大。所以我的建议是初学者先把动态规划解法吃透再去学习中心扩展两者互相印证之后对回文问题的理解会更立体。4. 实操踩坑边界条件与常见错误排查4.1 边界条件全梳理代码能跑通和能跑对是两个层面的问题。最长回文子串的边界条件非常容易出错我把常见的几种情况列一下你可以对照着检查自己的代码第一空字符串。输入为 时最长的回文子串是 长度是 0。很多人的代码在n 2的判断里直接返回 s这没问题但要注意 Python 里 n 为 0 时 s[0:0] 返回的是空字符串不会报错。第二单个字符。输入为 a 时最长回文子串就是 a 本身。这个在初始化 dp[i][i] True 时已经覆盖。第三所有字符都不相同。比如 abcde此时最长回文子串可以是任意一个字符长度是 1。动态规划代码中的 max_len 初始值必须设为 1否则可能返回空字符串。第四所有字符都相同。比如 aaaa最长回文子串是 aaaa 全长。这种用例是用来测试遍历顺序是否正确的绝佳测试用例因为它的所有子串都是回文只要遍历顺序错了答案就会出错。第五字符串长度恰好为 2 的情况。比如 aa 和 ab前者整个是回文后者只能取单个字符。ab 这类用例用来检查 length 2 的特殊分支是否处理正确。4.2 常见错误实录我自己踩过的坑这道题我刷了很多遍也帮别人 review 过代码这里整理几个反复出现的错误。第一个错误是忘记初始化 dp[i][i] True。如果跳过初始化当 length 3 时dp[i1][j-1] 可能引用了未初始化的 False导致最终结果漏掉很多回文串比如 aba 就会被误判为不是回文。这个错误很隐蔽因为结果不是直接报错而是返回了一个错误长度的子串。第二个错误是遍历顺序写反。有些人习惯性地把外层循环写成 i 从 0 到 n内层循环写成 j 从 0 到 n结果整个表格的依赖关系全乱了。这种错误最常见的表现是输入 aaaa 时只返回 aa而不是 aaaa。如果你遇到这种情况优先检查遍历顺序。第三个错误是在更新答案时只记录了长度没有记录起点导致最后不知道要从哪里切片。在动态规划表格里你完全可以在循环中顺便记录start变量关键是在每个dp[i][j]为 true 时都用j - i 1和当前max_len比较如果更大就更新start和max_len。第四个错误是想当然地尝试用一维滚动数组优化。最长回文子串的 dp[i][j] 依赖的是 dp[i1][j-1]也就是“下一行的前一个元素”。如果要压缩空间需要保留上一行的完整信息而且更新的方向必须是从左向右。这个优化思路是可以写出来的但远不如中心扩展法直接。新手阶段建议老老实实用二维数组先把逻辑理清楚再考虑空间优化。4.3 测试用例设计技巧写算法题设计一批有针对性的测试用例比盲目提交代码更能提升通过率。我常用的测试用例包括babad经典用例存在多个同长度的结果验证答案是否正确cbbd偶数长度回文 bb专门检验偶数分支a单字符边界ac无回文子串长度1的除外检验边界初始化aaaa全同字符检验遍历顺序abcba以中心为对称轴的奇数长度回文abacdfgdcaba其中包含 aba 和 abacdfgdcaba 不是回文但有回文前缀/后缀检验区间判断是否正确用这些用例跑一遍你的代码如果都能通过基本可以放心提交了。如果某个用例失败不要急着改代码先手动模拟一遍 dp 表格看看到底是哪一格的状态算错了这样排查起来更快。5. 从回文子串到 01 背包读懂动态规划的通用套路5.1 动态规划三要素状态、转移、边界很多人刷动态规划题时总觉得自己在背题换个题目就不会了。这是因为没有真正理解动态规划的通用套路。其实不管是最长回文子串还是热词里提到的 01 背包问题甚至是最长递增子序列、编辑距离它们都逃不出三件事状态定义、状态转移方程、边界条件与初始化。状态定义解决的是“我要求的是什么用什么样的数据结构来存储子问题的答案”。在最长回文子串里状态是 dp[i][j] 表示子串是否为回文在 01 背包里状态是 dp[i][w] 表示前 i 件物品在容量为 w 的背包里能够获得的最大价值。状态转移方程解决的是“大问题怎样由小问题推导出来”。在回文子串里是首尾字符相等且内部子串为回文在 01 背包里是“不选第 i 件物品”和“选第 i 件物品”两种决策取最大值。边界条件解决的是“最小子问题的答案是什么”。在回文子串里是单个字符 dp[i][i] True在 01 背包里是 dp[0][w] 0因为没有物品可选时价值为 0。这三者缺一不可。状态定义错了转移方程一定错转移方程对但边界没初始化结果还是错。所以你在学习任何一道动态规划题时建议自问三个问题这个状态定义合理吗转移方程是怎么推导出来的最小的子问题怎么处理能把这三个问题回答清楚基本就掌握了这道题。5.2 01 背包的状态模型选与不选01 背包问题是一个几乎每本算法书都会收录的经典动态规划题目。问题描述是这样的有 n 件物品和一个容量为 W 的背包每件物品有自己的重量 w[i] 和价值 v[i]问怎样选择物品装入背包能让背包中的总价值最大而且每件物品最多只能选一次。它的状态定义是 dp[i][j] 表示从前 i 件物品中选择一些放入容量为 j 的背包中能获得的最大价值。转移方程有两种情况不选第 i 件物品那么 dp[i][j] dp[i-1][j]选第 i 件物品前提是 j w[i]那么 dp[i][j] dp[i-1][j-w[i]] v[i]。取这两个中的较大值即可。对照回文子串的转移方程你会发现本质上是同一件事一个问题是“同一区间的回文性依赖内部区间的回文性”另一个问题是“当前物品选不选依赖前 i-1 件物品的选择结果”。它们都是通过分治的思想把复杂的原问题拆分成规模更小的子问题再通过查表的方式避免重复计算。区别在于状态依赖的方向。回文子串是“区间右下角依赖区间左下角”方向是斜向的所以遍历顺序要按长度从小到大01 背包是“当前行依赖上一行”方向是纵向的所以遍历顺序是外层物品、内层容量。理解了这个依赖方向你就知道为什么有些动态规划可以滚动数组优化有些不能。5.3 怎么判断一道题能不能用动态规划实际做题的经验多了之后你会发现动态规划适用的题目通常有两个典型特征。第一个特征是最优子结构原问题的最优解包含子问题的最优解。在最长回文子串中如果 s[i..j] 是回文那么 s[i1..j-1] 也必须是回文这就是一种最优子结构。在 01 背包中如果前 i 件物品在容量 j 下的最优解选择了第 i 件物品那么去掉它之后的前 i-1 件物品必须在容量 j-w[i] 下达到最优否则可以替换成更优的解。如果一个题目里子问题的最优解不能被复用那动态规划就不太适用。第二个特征是重叠子问题。在暴力求解过程中同一个子问题会被反复计算很多次。比如判断 aba 和 ababa 是否为回文时内部都会判断 b 是否为回文。如果每次都用递归重新计算重复工作量非常大。动态规划通过用一个表格把子问题的答案存起来每次需要时直接查表这就是“以空间换时间”的本质。这两个特征缺一不可。有些题目有最优子结构但子问题不重叠比如归并排序那就适合用分治而不是动态规划有些题目子问题重叠但没有最优子结构比如一些贪心问题那就不能强制用动态规划。5.4 刷题建议与学习路径如果你是刚接触动态规划我给的建议是不要一上来就刷一堆难题先把几个最经典的问题吃透。最长回文子串是一个非常好的入门题因为它状态定义直观转移方程简单边界也少而且和中心扩展法形成了互补。我自己的学习路径是这样的先做最长回文子串把二维 DP 的表格法练熟然后做 01 背包理解一维滚动数组的优化技巧再做最长递增子序列和编辑距离。这四个题目覆盖了动态规划最常见的几种模式区间 DP、线性 DP、双序列 DP。熟练掌握这四类之后再去刷 LeetCode 上 tag 为动态规划的题目会顺畅很多。关于刷题频率我的体会是动态规划需要“温故而知新”。同一道题隔两三个月再刷一遍你可能会发现以前没注意到的细节。我至今还会偶尔回来重新做一遍最长回文子串每次都会有不同的理解深度。6. 再聊聊我第一次做这道题时的经历我第一次接触最长回文子串是在一次面试前的集中刷题阶段。当时我对动态规划的理解基本停留在“背包问题”上看到这道题完全不知道从哪里下手暴力解提交之后果然超时。后来我去看题解看了三遍状态转移方程才看懂为什么 dp[i][j] 要写成那样又调试了大半天才搞明白遍历顺序的问题。现在回头看这道题把动态规划的关键要素都串起来了状态定义要有意义转移方程要靠推导而不靠死记遍历顺序由依赖关系决定边界条件要在写代码之前就想清楚。给一个还没有入门的读者说句实在话如果你能在一张草稿纸上手工模拟一个长度为 5 的字符串的 dp 表格填表过程每填一格都能说出为什么是这个值那这道题你基本就掌握了。一个小技巧是把 dp 表格画出来用行表示 i列表示 j然后把对角线先涂成 true再按照长度从短到长的顺序依次填充。你会发现表格是“沿着对角线一层一层往右上角填”的这种感觉比单纯读代码要直观得多。我每次教别人动态规划都会让他们先画表格再写代码效果比直接讲公式好太多。