动态规划专题：回文串问题与区间 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] 时：
    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 代码实现

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;
    }
};

---

三、最长回文子串 (Medium)

3.1 题目描述

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

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

示例：

• 输入："babad" -> 输出："bab" 或 "aba"

3.2 思路

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

3.3 代码实现

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);
    }
};

---

四、回文串分割 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 代码实现

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;
    }
};

---

五、分割回文串 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 代码实现

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];
    }
};

---

六、最长回文子序列 (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 代码实现

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];
    }
};

---

七、让字符串成为回文串的最小插入次数 (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)

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 的核心在于**'剥洋葱'**。

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