【动态规划】专题(七)：回文串问题——对称之美与区间 DP
文章目录
区间 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]时：- 如果
i == j(长度1)：true。 - 如果
i + 1 == j(长度2)：true。 - 如果长度 > 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 思路：预处理 + 枚举
- 预处理：先用 O(N²) 的时间把
dp[i][j]表填好（是否回文）。 - 暴力枚举：切两刀。
- 第一刀切在
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
这题需要两步走：
- 预处理：用
isPal[i][j]记录区间是否回文（O(N²)）。 - 线性 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]内的最长回文子序列长度。 - 转移：
s[i] == s[j]：两头匹配了，长度 +2，然后看里面。dp[i][j] = dp[i+1][j-1] + 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]变回文的最小插入次数。 - 转移：
s[i] == s[j]：两头本来就匹配，不需要插入。看里面。dp[i][j] = dp[i+1][j-1]。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 的核心在于**“剥洋葱”**。
- 子串 vs 子序列：
- 子串 (Substring)：连续。
s[i] == s[j]时才能扩展，否则直接 false。 - 子序列 (Subsequence)：不连续。
s[i] != s[j]时可以舍弃一边取最大值。
- 子串 (Substring)：连续。
- 填表顺序：
一定要牢记从下往上（i逆序，j正序），保证计算dp[i][j]时，它左下角的dp[i+1][j-1]已经算好了。
下一篇，我们将进入双数组 DP（最长公共子序列 LCS 系列）。那是另一个经典的二维 DP 模型，专门解决两个字符串/数组的匹配问题。准备好迎接挑战了吗？ 🚀
