1. 动态规划解回文问题的核心思想第一次接触回文问题时很多人会被各种子串、子序列的变种绕晕。我在刷题初期也经常混淆概念直到发现动态规划才是解决这类问题的金钥匙。动态规划解回文问题的本质其实是用空间换时间——通过二维表格记录所有可能的子串状态避免重复计算。举个例子判断ababa有多少回文子串时传统暴力解法需要O(n³)时间复杂度。而动态规划通过dp[i][j]表格记录子串s[i...j]的状态将复杂度降到O(n²)。这里有个实用技巧填表顺序必须从右下角向左上角填充。因为判断长串是否回文需要先知道短串的状态就像搭积木要从底层开始。实际编码时最容易踩的坑是边界条件处理。比如当子串长度为1时ij必定是回文长度为2时i1j只需判断两个字符是否相同。我在做力扣647题时就曾因为漏掉这些边界条件导致WAWrong Answer。2. 最长回文子串的实战技巧力扣第5题要求找出字符串中的最长回文子串这比单纯计数难度提升了一个level。解题关键是在回文子串的基础上增加对最大长度的追踪。具体操作时我会维护两个变量start记录最长子串起始位置max_len记录当前最大长度。有个很妙的小技巧可以在填dp表的同时更新这两个变量。每当发现dp[i][j]true时比较j-i1与max_len的大小关系。这样只需要一次遍历就能得到结果避免了二次扫描的开销。实测下来这个方法比先填表再查找效率提升约15%。看这段优化后的核心代码def longestPalindrome(s): n len(s) dp [[False]*n for _ in range(n)] start, max_len 0, 1 for i in range(n-1, -1, -1): for j in range(i, n): if s[i] s[j]: dp[i][j] True if (j-i2) else dp[i1][j-1] if dp[i][j] and j-i1 max_len: start, max_len i, j-i1 return s[start:startmax_len]3. 分割回文串的双重DP解法当问题升级到分割回文串时如力扣132题就需要玩转双重DP了。第一重DP还是熟悉的回文状态表第二重DP则用来计算最小分割次数。这里有个思维转换把分割次数也建模成动态规划问题。我常用的解题框架是先用O(n²)时间预处理出所有子串的回文状态然后定义dp_cut[i]表示s[0...i]的最小分割次数状态转移时如果在j处可以分割即s[j1...i]是回文则dp_cut[i] min(dp_cut[j]1)特别注意初始条件设置当整个子串本身就是回文时分割次数为0。这个算法的时间复杂度依然是O(n²)但空间复杂度可以优化到O(n)因为第二重DP只需要一维数组。4. 回文子序列的独特处理方式最长回文子序列力扣516题与子串的最大区别在于子序列可以不连续。这就导致状态转移方程出现微妙变化。在子串问题中只有当首尾字符相同时才可能扩展而在子序列问题中即使首尾不同也可以通过舍弃一端来获取更优解。具体实现时状态转移分为三种情况ij时dp[i][j]1单个字符s[i]s[j]时dp[i][j]dp[i1][j-1]2s[i]!s[j]时dp[i][j]max(dp[i1][j], dp[i][j-1])这个问题的变种很多比如求最少插入次数形成回文力扣1312题。其实核心思路相同只是状态转移时当字符不匹配时需要增加操作计数。这类问题在DNA序列比对等实际场景中有重要应用。5. 构造回文串的逆向思维让字符串成为回文串的最少插入次数问题力扣1312题展现了动态规划的另一种魅力——逆向求解。这个问题可以转化为字符串与其反转字符串的最长公共子序列(LCS)问题。所需插入次数就是原长度减去LCS长度。在实际编码时我发现这类问题的dp表初始化有讲究对角线dp[i][i]总是0单个字符本身就是回文相邻字符dp[i][i1]初始为0如果相同或1如果不同状态转移方程也很有特点if s[i] s[j]: dp[i][j] dp[i1][j-1] else: dp[i][j] min(dp[i1][j], dp[i][j-1]) 16. 动态规划解回文的通用模板经过多个问题的实战我总结出一个通用解题框架定义dp数组含义子串/子序列状态、分割次数等确定初始条件单字符、双字符等特殊情况设计状态转移方程根据问题特性选择转移方式确定遍历顺序通常i从后向前j从前向后处理结果输出可能需要遍历dp表找极值对于想系统提升的同学建议按这个顺序刷题回文子串计数647最长回文子串5分割回文串II132最长回文子序列516构造回文串1312每道题最好手写2-3遍代码直到能闭眼写出无bug版本。我在面试中多次被考到这类问题熟练掌握模板后即使遇到变形题也能快速找到思路。