C++算法
动态规划专题：回文串问题与区间 DP
动态规划中回文串问题的核心是区间 DP，状态定义为 dp[i][j] 表示区间 [i, j] 的某种属性。内容涵盖回文子串统计、最长回文子串查找、字符串分割成回文串的最小次数以及最长回文子序列计算。解题关键在于利用 s[i] 和 s[j] 是否相等进行状态转移，配合预处理回文表优化查询效率。文中提供了 C++ 代码实现及详细思路分析。
动态规划中回文串问题的核心是区间 DP，状态定义为 dp[i][j] 表示区间 [i, j] 的某种属性。内容涵盖回文子串统计、最长回文子串查找、字符串分割成回文串的最小次数以及最长回文子序列计算。解题关键在于利用 s[i] 和 s[j] 是否相等进行状态转移，配合预处理回文表优化查询效率。文中提供了 C++ 代码实现及详细思路分析。
开篇：之前的线性 DP（如斐波那契、LIS），状态往往是
dp[i]，表示"以i结尾…"。思维升级：到了回文串，我们关注的是两头。
s[i]和s[j]如果相等，那就看里面的[i+1, j-1]是不是回文；如果不等，那就不是。所以，状态定义通常是dp[i][j]表示区间[i, j]的某种属性。
题目链接：647. 回文子串
描述：统计字符串中回文子串的数目。
示例：
- 输入：
"abc"-> 输出：3(a,b,c)- 输入：
"aaa"-> 输出：6(a,a,a,aa,aa,aaa)
dp[i][j] (bool) 表示 s[i...j] 是否是回文串。s[i] == s[j] 时：
i == j (长度 1)：true。i + 1 == j (长度 2)：true。dp[i+1][j-1]。s[i] != s[j] 时：false。dp[i][j] 依赖 dp[i+1][j-1]（左下角），所以 i 必须从大到小（从下往上）遍历，j 从 i 开始往右遍历。class Solution {
public:
int countSubstrings(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;
}
};
题目链接：5. 最长回文子串
描述：找最长的回文子串，返回具体字符串。
示例：
- 输入：
"babad"-> 输出："bab"或"aba"
这题其实就是上一题的"副产品"。在上一题填表的过程中，如果 dp[i][j] == true，我们就记录一下当前的长度 len = j - i + 1 和起始位置 begin = i，维护一个最大值即可。
class Solution {
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);
}
};
题目链接：1745. 回文串分割 IV
描述：能否把字符串
s分割成 3 个非空 回文子串？
dp[i][j] 表填好（是否回文）。i 后面。j 后面。s[0...i], s[i+1...j], s[j+1...n-1] 是否都是回文。dp 即可，判断是 O(1) 的。class Solution {
public:
bool checkPartitioning(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 - 2
for (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]) {
return true;
}
}
}
return false;
}
};
题目链接：132. 分割回文串 II
描述：将
s分割成若干回文子串，求最少分割次数。
这题需要两步走：
isPal[i][j] 记录区间是否回文（O(N²)）。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)。class Solution {
public:
int minCut(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 {
// 枚举分割点 j
for (int j = 1; j <= i; j++) {
if (isPal[j][i]) {
f[i] = min(f[i], f[j - 1] + 1);
}
}
}
}
return f[n - 1];
}
};
题目链接：516. 最长回文子序列
描述：找出最长的回文子序列（可以不连续）。
示例：
- 输入：
"bbbab"-> 输出：4(bbbb)
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）。class Solution {
public:
int longestPalindromeSubseq(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];
}
};
描述：任意位置插入字符，变成回文串。求最少次数。
示例：
- 输入：
"mbadm"-> 输出：2(mbdadbm)
思路 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。class Solution {
public:
int minInsertions(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 的核心在于**'剥洋葱'**。
s[i] == s[j] 时才能扩展，否则直接 false。s[i] != s[j] 时可以舍弃一边取最大值。i 逆序，j 正序），保证计算 dp[i][j] 时，它左下角的 dp[i+1][j-1] 已经算好了。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online