【动态规划】专题(七)：回文串问题——对称之美与区间 DP

文章目录

• 区间 DP 入门：从中心向两边扩散
• 一、 前言：区间 DP 的套路
• 二、 回文子串 (Medium)
  • 2.1 题目描述
  • 2.2 核心思路：区间 DP 预处理
  • 2.3 代码实现
• 三、 最长回文子串 (Medium)
  • 3.1 题目描述
  • 3.2 思路
  • 3.3 代码实现
• 四、 回文串分割 IV (Hard)
  • 4.1 题目描述
  • 4.2 思路：预处理 + 枚举
  • 4.3 代码实现
• 五、 分割回文串 II (Hard)
  • 5.1 题目描述
  • 5.2 组合拳：区间 DP + 线性 DP
  • 5.3 代码实现
• 六、 最长回文子序列 (Medium)
  • 6.1 题目描述
  • 6.2 状态转移
  • 6.3 代码实现
• 七、 让字符串成为回文串的最小插入次数 (Hard)
  • 7.1 题目描述
  • 7.2 两种思路
  • 7.3 代码实现 (思路 B)
• 八、 总结

区间 DP 入门：从中心向两边扩散

一、 前言：区间 DP 的套路

💬 开篇：之前的线性 DP（如斐波那契、LIS），状态往往是 dp[i]，表示"以 i 结尾…"。

🚀 思维升级：到了回文串，我们关注的是两头。s[i] 和 s[j] 如果相等，那就看里面的 [i+1, j-1] 是不是回文；如果不等，那就不是。所以，状态定义通常是 dp[i][j] 表示区间 [i, j] 的某种属性。

二、 回文子串 (Medium)

2.1 题目描述

题目链接：647. 回文子串

描述：
统计字符串中回文子串的数目。

示例：
输入："abc" -> 输出：3 (a, b, c)
输入："aaa" -> 输出：6 (a, a, a, aa, aa, aaa)

2.2 核心思路：区间 DP 预处理

• 状态：dp[i][j] (bool) 表示 s[i...j] 是否是回文串。
• 转移：
  s[i] == s[j] 时：
  1. 如果 i == j (长度1)：true。
  2. 如果 i + 1 == j (长度2)：true。
  3. 如果长度 > 2：看里面 dp[i+1][j-1]。
     s[i] != s[j] 时：false。
• 填表顺序：
  由于 dp[i][j] 依赖 dp[i+1][j-1]（左下角），所以 i 必须从大到小（从下往上）遍历，j 从 i 开始往右遍历。

2.3 代码实现

classSolution{public:intcountSubstrings(string s){int n = s.size();// dp[i][j] 表示 s[i...j] 是否为回文 vector<vector<bool>>dp(n,vector<bool>(n,false));int count =0;// i 从下往上for(int i = n -1; i >=0; i--){// j 从左往右 (j >= i)for(int j = i; j < n; j++){if(s[i]== s[j]){// 1. 只有一个字符 or 两个字符 -> 肯定是回文// 2. 多个字符 -> 看内部if(j - i <2|| dp[i +1][j -1]){ dp[i][j]=true; count++;}}}}return count;}};

三、 最长回文子串 (Medium)

3.1 题目描述

题目链接：5. 最长回文子串

描述：
找最长的回文子串，返回具体字符串。

示例：
输入："babad" -> 输出："bab" 或 "aba"

3.2 思路

这题其实就是上一题的"副产品"。
在上一题填表的过程中，如果 dp[i][j] == true，我们就记录一下当前的长度 len = j - i + 1 和起始位置 begin = i，维护一个最大值即可。

3.3 代码实现

classSolution{public: string longestPalindrome(string s){int n = s.size(); vector<vector<bool>>dp(n,vector<bool>(n,false));int maxLen =1;int begin =0;for(int i = n -1; i >=0; i--){for(int j = i; j < n; j++){if(s[i]== s[j]){if(j - i <2|| dp[i +1][j -1]){ dp[i][j]=true;// 更新最大长度if(j - i +1> maxLen){ maxLen = j - i +1; begin = i;}}}}}return s.substr(begin, maxLen);}};

四、 回文串分割 IV (Hard)

4.1 题目描述

题目链接：1745. 回文串分割 IV

描述：
能否把字符串 s 分割成 3 个非空 回文子串？

4.2 思路：预处理 + 枚举

1. 预处理：先用 O(N²) 的时间把 dp[i][j] 表填好（是否回文）。
2. 暴力枚举：切两刀。
   • 第一刀切在 i 后面。
   • 第二刀切在 j 后面。
   • 检查三段：s[0...i], s[i+1...j], s[j+1...n-1] 是否都是回文。
   • 只要查表 dp 即可，判断是 O(1) 的。

4.3 代码实现

classSolution{public:boolcheckPartitioning(string s){int n = s.size(); vector<vector<bool>>dp(n,vector<bool>(n,false));// 1. 预处理 dp 表for(int i = n -1; i >=0; i--){for(int j = i; j < n; j++){if(s[i]== s[j]){ dp[i][j]=(j - i <2)|| dp[i +1][j -1];}}}// 2. 枚举两个分割点 i 和 j// s[0...i] | s[i+1...j] | s[j+1...n-1]// i 至少留出后面两个字符的空间，所以 i < n - 2for(int i =0; i < n -2; i++){if(!dp[0][i])continue;// 第一段不是回文，剪枝for(int j = i +1; j < n -1; j++){if(dp[i +1][j]&& dp[j +1][n -1]){returntrue;}}}returnfalse;}};

五、 分割回文串 II (Hard)

5.1 题目描述

题目链接：132. 分割回文串 II

描述：
将 s 分割成若干回文子串，求最少分割次数。

5.2 组合拳：区间 DP + 线性 DP

这题需要两步走：

1. 预处理：用 isPal[i][j] 记录区间是否回文（O(N²)）。
2. 线性 DP：f[i] 表示 s[0...i] 的最少分割次数。

f[i] 的转移：
枚举最后一段回文串的起点 j (0 <= j <= i)：
如果 s[j...i] 是回文（查表 isPal[j][i]）：

• 若 j == 0，说明整体回文，不需要分割，f[i] = 0。
• 若 j > 0，f[i] = min(f[i], f[j-1] + 1)。

5.3 代码实现

classSolution{public:intminCut(string s){int n = s.size();// 1. 预处理回文表 vector<vector<bool>>isPal(n,vector<bool>(n,false));for(int i = n -1; i >=0; i--){for(int j = i; j < n; j++){if(s[i]== s[j]){ isPal[i][j]=(j - i <2)|| isPal[i +1][j -1];}}}// 2. 线性 DP 求最小分割 vector<int>f(n, INT_MAX);for(int i =0; i < n; i++){// 如果 0...i 直接是回文，分割 0 次if(isPal[0][i]){ f[i]=0;}else{// 枚举分割点 jfor(int j =1; j <= i; j++){if(isPal[j][i]){ f[i]=min(f[i], f[j -1]+1);}}}}return f[n -1];}};

六、 最长回文子序列 (Medium)

6.1 题目描述

题目链接：516. 最长回文子序列

描述：
找出最长的回文子序列（可以不连续）。

示例：
输入："bbbab" -> 输出：4 (bbbb)

6.2 状态转移

• 状态：dp[i][j] 表示 s[i...j] 内的最长回文子序列长度。
• 转移：
  1. s[i] == s[j]：两头匹配了，长度 +2，然后看里面。
     dp[i][j] = dp[i+1][j-1] + 2。
  2. s[i] != s[j]：两头不匹配，说明 s[i] 和 s[j] 至少有一个不在最长序列里。
     要么舍弃左边 (dp[i+1][j])，要么舍弃右边 (dp[i][j-1])。
     dp[i][j] = max(dp[i+1][j], dp[i][j-1])。
• 初始化：dp[i][i] = 1（单个字符长度为 1）。

6.3 代码实现

classSolution{public:intlongestPalindromeSubseq(string s){int n = s.size(); vector<vector<int>>dp(n,vector<int>(n,0));for(int i = n -1; i >=0; i--){ dp[i][i]=1;// 初始化对角线for(int j = i +1; j < n; j++){if(s[i]== s[j]){ dp[i][j]= dp[i +1][j -1]+2;}else{ dp[i][j]=max(dp[i +1][j], dp[i][j -1]);}}}return dp[0][n -1];}};

七、 让字符串成为回文串的最小插入次数 (Hard)

7.1 题目描述

题目链接：1312. 让字符串成为回文串的最少插入次数

描述：
任意位置插入字符，变成回文串。求最少次数。

示例：
输入："mbadm" -> 输出：2 (mbdadbm)

7.2 两种思路

思路 A：最长回文子序列的补集
想让插入次数最少，也就是要保留最多的字符不动。
保留谁？当然是最长回文子序列。
答案 = 总长度 - 最长回文子序列长度。
直接套用上一题代码即可。

思路 B：正向区间 DP

• 状态：dp[i][j] 表示让 s[i...j] 变回文的最小插入次数。
• 转移：
  1. s[i] == s[j]：两头本来就匹配，不需要插入。看里面。
     dp[i][j] = dp[i+1][j-1]。
  2. s[i] != s[j]：
     • 要么在右边插一个 s[i]：次数 = dp[i+1][j] + 1。
     • 要么在左边插一个 s[j]：次数 = dp[i][j-1] + 1。
     • 取最小值。

7.3 代码实现 (思路 B)

classSolution{public:intminInsertions(string s){int n = s.size(); vector<vector<int>>dp(n,vector<int>(n,0));for(int i = n -1; i >=0; i--){for(int j = i +1; j < n; j++){if(s[i]== s[j]){ dp[i][j]= dp[i +1][j -1];}else{ dp[i][j]=min(dp[i +1][j], dp[i][j -1])+1;}}}return dp[0][n -1];}};

八、 总结

💬 总结：回文串 DP 的核心在于**“剥洋葱”**。

1. 子串 vs 子序列：
   • 子串 (Substring)：连续。s[i] == s[j] 时才能扩展，否则直接 false。
   • 子序列 (Subsequence)：不连续。s[i] != s[j] 时可以舍弃一边取最大值。
2. 填表顺序：
   一定要牢记从下往上（i 逆序，j 正序），保证计算 dp[i][j] 时，它左下角的 dp[i+1][j-1] 已经算好了。

下一篇，我们将进入双数组 DP（最长公共子序列 LCS 系列）。那是另一个经典的二维 DP 模型，专门解决两个字符串/数组的匹配问题。准备好迎接挑战了吗？ 🚀