LeetCode刷题笔记：用动态规划一口气搞定6道回文串问题（附Java代码）

动态规划解回文问题从子串到子序列的通用解法回文串问题在算法面试中出现的频率居高不下无论是统计回文子串数量、寻找最长回文子串还是处理回文子序列动态规划(DP)都是解决这类问题的利器。本文将带你系统掌握六种经典回文问题的动态规划解法通过对比分析它们的共性与差异形成一套可复用的解题框架。1. 动态规划解回文问题的核心思路动态规划解回文问题的关键在于状态定义和状态转移方程的建立。我们先从一个基础问题入手逐步扩展到更复杂的场景。1.1 回文子串的基本DP解法对于判断子串是否为回文最常用的DP方法是构建一个二维数组dp[i][j]表示字符串从索引i到j的子串是否为回文。状态转移方程如下if (s[i] s[j]) { dp[i][j] dp[i1][j-1]; // 取决于内部子串 } else { dp[i][j] false; }边界条件单个字符dp[i][i] true两个相同字符dp[i][i1] true1.2 填表顺序的技巧由于dp[i][j]依赖于dp[i1][j-1]我们需要从下往上、从左往右填表for (int i n - 1; i 0; i--) { for (int j i; j n; j) { // 填充dp[i][j] } }这种填表顺序确保了在计算dp[i][j]时dp[i1][j-1]已经被计算过。2. 统计回文子串数量LeetCode 6472.1 问题描述给定一个字符串计算其中回文子串的总数。具有不同起始或结束位置的子串即使由相同的字符组成也会被视作不同的子串。2.2 解法优化在基础DP解法上稍作修改统计所有dp[i][j]为true的情况public int countSubstrings(String s) { int n s.length(); boolean[][] dp new boolean[n][n]; int count 0; for (int i n - 1; i 0; i--) { for (int j i; j n; j) { if (s.charAt(i) s.charAt(j)) { dp[i][j] (j - i 2) || dp[i 1][j - 1]; } if (dp[i][j]) count; } } return count; }提示对于长度≤2的子串可以直接判断是否为回文无需查看内部子串。3. 寻找最长回文子串LeetCode 53.1 问题升级在统计回文子串的基础上我们需要记录最长回文的起始位置和长度。3.2 代码实现public String longestPalindrome(String s) { int n s.length(); boolean[][] dp new boolean[n][n]; int maxLen 0; int start 0; for (int i n - 1; i 0; i--) { for (int j i; j n; j) { if (s.charAt(i) s.charAt(j)) { dp[i][j] (j - i 2) || dp[i 1][j - 1]; } if (dp[i][j] j - i 1 maxLen) { maxLen j - i 1; start i; } } } return s.substring(start, start maxLen); }3.3 复杂度分析指标值时间复杂度O(n²)空间复杂度O(n²)最优解Manacher算法(O(n))4. 回文子序列问题LeetCode 5164.1 问题差异与回文子串不同子序列不要求字符连续。这导致状态转移方程有所变化if (s[i] s[j]) { dp[i][j] 2 dp[i1][j-1]; } else { dp[i][j] Math.max(dp[i1][j], dp[i][j-1]); }4.2 完整实现public int longestPalindromeSubseq(String s) { int n s.length(); int[][] dp new int[n][n]; for (int i n - 1; i 0; i--) { dp[i][i] 1; for (int j i 1; j n; j) { if (s.charAt(i) s.charAt(j)) { dp[i][j] 2 dp[i 1][j - 1]; } else { dp[i][j] Math.max(dp[i 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; }4.3 关键区别特征回文子串回文子序列连续性必须连续可以不连续DP值类型booleanint状态转移依赖内部子串取左右最大值5. 回文分割问题LeetCode 1325.1 问题描述给定一个字符串将字符串分割成一些子串使每个子串都是回文返回符合要求的最少分割次数。5.2 双重DP解法先用DP预处理所有可能的回文子串再用DP计算到每个位置的最小分割次数public int minCut(String s) { int n s.length(); boolean[][] isPal new boolean[n][n]; int[] dp new int[n]; // 预处理回文信息 for (int i n - 1; i 0; i--) { for (int j i; j n; j) { if (s.charAt(i) s.charAt(j) (j - i 2 || isPal[i 1][j - 1])) { isPal[i][j] true; } } } // 计算最小分割 for (int i 0; i n; i) { if (isPal[0][i]) { dp[i] 0; } else { dp[i] i; // 初始化为最大可能分割次数 for (int j 0; j i; j) { if (isPal[j 1][i]) { dp[i] Math.min(dp[i], dp[j] 1); } } } } return dp[n - 1]; }注意预处理回文信息可以避免在计算最小分割时重复判断子串是否为回文。6. 构建回文的最小插入次数LeetCode 13126.1 问题转化这个问题可以转化为求字符串与其反转字符串的最长公共子序列(LCS)然后用字符串长度减去LCS长度。6.2 DP解法public int minInsertions(String s) { int n s.length(); int[][] dp new int[n][n]; for (int i n - 1; i 0; i--) { for (int j i 1; j n; j) { if (s.charAt(i) s.charAt(j)) { dp[i][j] dp[i 1][j - 1]; } else { dp[i][j] Math.min(dp[i 1][j], dp[i][j - 1]) 1; } } } return dp[0][n - 1]; }6.3 解题思路对比问题类型解题关键DP表含义回文子串统计判断所有子串是否为回文最长回文子串记录最大长度是否为回文回文子序列不连续字符最长长度回文分割预处理分割DP最小分割数构建回文逆向思考最小操作数7. 综合应用与解题模板通过分析以上问题我们可以总结出一个通用的DP解回文问题的框架确定DP表含义根据问题选择boolean或int类型初始化边界条件单个字符或两个字符的情况确定填表顺序通常从下往上、从左往右状态转移方程对于子串问题dp[i][j] (s[i]s[j]) dp[i1][j-1]对于子序列问题考虑字符相等和不相等两种情况根据问题需求处理结果统计数量、记录最大值、计算最小值等7.1 代码模板public int solvePalindromeProblem(String s) { int n s.length(); // 1. 定义DP表 int[][] dp new int[n][n]; // 或 boolean[][] // 2. 填表 for (int i n - 1; i 0; i--) { for (int j i; j n; j) { // 3. 处理边界条件 if (i j) { dp[i][j] 1; // 或 true continue; } // 4. 状态转移 if (s.charAt(i) s.charAt(j)) { // 根据问题类型实现不同逻辑 } else { // 根据问题类型实现不同逻辑 } } } // 5. 返回结果 return dp[0][n - 1]; // 或其他处理 }7.2 常见变种与应对策略空间优化有些问题可以将二维DP优化为一维预处理技巧对于复杂问题可以先预处理回文信息反向思考如最小插入次数问题可以转化为求最长回文子序列多步DP像分割问题可能需要多个DP表协同工作在实际面试中理解这些问题的共性和差异能够快速识别问题类型并套用相应模板可以显著提高解题效率。建议按照本文的顺序练习这些问题体会动态规划解回文问题的精妙之处。