动态规划专题：回文串问题与区间 DP

二、最长回文子串 (Medium)

题目描述

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

示例： 输入："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);
    }
};

三、回文串分割 IV (Hard)

题目描述

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

思路：预处理 + 枚举

1. 预处理：先用 O(N²) 的时间把 dp[i][j] 表填好（是否回文）。
2. 暴力枚举：切两刀。
   • 第一刀切在 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;
    }
};

四、分割回文串 II (Hard)

题目描述

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

组合拳：区间 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)。

代码实现

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)

题目描述

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

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

状态转移

• 状态：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）。

代码实现

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)

题目描述

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

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

两种思路

思路 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。
     • 取最小值。

代码实现 (思路 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] 已经算好了。

这类二维 DP 模型非常经典，掌握后对处理 LCS 系列或其他字符串匹配问题会有很大帮助。