LeetCode LCR 094. 分割回文串 II

约 8 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 困难 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 动态规划 LCR
目录

题目描述

✅ LCR 094. 分割回文串 II

题意分析

把字符串 s 切成若干段，要求每一段都是回文串，问最少切几刀。注意问的是刀数不是段数，切 k 刀会得到 k + 1 段，两者差 1，读题时最容易在这里丢分。

约束信号是「每一段都必须合法」外加「求最优值而不是求所有方案」。前者说明段与段之间是独立的，一段选定之后剩下的问题形态不变，具备最优子结构；后者说明不需要枚举方案，只要在状态之间取最小值。

边界要留意：单个字符本身就是回文，所以答案上界是 n - 1（每个字符各成一段）；整串本身是回文时答案是 0；字符串长度可以到 2000，意味着 $O(n^2)$ 可行、$O(n^3)$ 有超时风险。

解法：回文预处理加动态规划

核心思路

暴力做法是枚举所有切法，段数是指数级的，显然不行。退一步用回溯枚举每一段的结尾，仍然是指数级。

换成 DP 的思路：只关心最少刀数，那么处理到前缀 s[0..i] 时，唯一需要做的决策是「最后一段从哪里开始」。设最后一段是 s[j..i] 且它是回文，那么这个方案的刀数就是「前缀 s[0..j-1] 的最少刀数」再加上 j 前面这一刀。当 j == 0 时整个前缀自成一段，一刀都不用切。

于是状态定义为：dp[i] 表示把前缀 s[0..i] 全部切成回文段所需的最少刀数。转移是 dp[i] = min(dp[j-1] + 1)，j 取遍所有让 s[j..i] 为回文的位置；若 s[0..i] 整体就是回文，则 dp[i] = 0。

直接这样写还有一个瓶颈：转移里每次判断 s[j..i] 是否回文要 $O(n)$，总复杂度 $O(n^3)$。所以先把判定预处理成表——pal[left][right] 表示 s[left..right] 是否回文，递推关系是 pal[l][r] = (s[l] == s[r]) && (r - l <= 2 || pal[l+1][r-1])。r - l <= 2 这一支覆盖长度 1、2、3 的短区间，它们只要两端字符相等就一定回文，不必再往里看。预处理本身是 $O(n^2)$，之后每次判定就变成 $O(1)$ 查表。

预处理的枚举顺序必须让短区间先算完：外层 right 从小到大，内层 left 从 0 到 right，此时 pal[left+1][right-1] 所在的列 right - 1 已经在上一轮全部算好。

解题步骤

  • 开一个 n × n 的布尔表 pal，外层枚举右端点 right、内层枚举左端点 left，按上面的递推填表。顺序必须是右端点递增，才能保证 right - 1 那一列已就绪。
  • 开一个长度 n 的 dp，把 dp[i] 初始化成 i。这个初值正好对应「前 i + 1 个字符各自成段」，切 i 刀，是一个天然安全的上界，比用无穷大更省事。
  • 从左到右枚举前缀结尾 i，再枚举最后一段的起点 j（从 0 到 i）。枚举起点而不是终点，是为了让「剩余部分」永远是一个更短的前缀，正好对应已算好的状态。
  • 若 pal[j][i] 为假就跳过，这个 j 不构成合法的最后一段。
  • 若 j == 0，说明整个 s[0..i] 就是一段回文，dp[i] = 0，这是可能的最小值，直接置零。
  • 否则用 dp[j-1] + 1 更新 dp[i]。这里的 +1 就是 j 前面那一刀，dp[j-1] 是剩余前缀的最优解。
  • 最终答案是 dp[n-1]。

以 s = "aab" 走一遍：n = 3。先填回文表。right = 0：left = 0 时两端同字符、长度 1，pal[0][0] = true。right = 1：left = 0 时 s[0] = 'a' 等于 s[1] = 'a' 且长度 2，pal[0][1] = true；left = 1 时 pal[1][1] = true。right = 2：left = 0 时 'a' 与 'b' 不等，为假；left = 1 时 'a' 与 'b' 不等，为假；left = 2 时 pal[2][2] = true。

再跑 DP。i = 0：初值 dp[0] = 0，j = 0 时 pal[0][0] 为真且 j == 0，dp[0] = 0。

i = 1：初值 dp[1] = 1。j = 0 时 pal[0][1] 为真且 j == 0，dp[1] = 0（"aa" 整体就是回文，不用切）。j = 1 时 pal[1][1] 为真，候选 dp[0] + 1 = 1，不优于 0，dp[1] 保持 0。

i = 2：初值 dp[2] = 2。j = 0 时 pal[0][2] 为假，跳过。j = 1 时 pal[1][2] 为假，跳过。j = 2 时 pal[2][2] 为真，候选 dp[1] + 1 = 0 + 1 = 1，比 2 小，dp[2] = 1。

返回 dp[2] = 1。核对方案：切成 "aa" 和 "b" 两段，两段都是回文，中间切一刀，答案确实是 1。

代码实现

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] pal = new boolean[n][n];
        for (int right = 0; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right) && (right - left <= 2 || pal[left + 1][right - 1])) {
                    pal[left][right] = true;
                }
            }
        }

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = i;
            for (int j = 0; j <= i; j++) {
                if (!pal[j][i]) {
                    continue;
                }
                if (j == 0) {
                    dp[i] = 0;
                } else {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}

func minCut(s string) int {
    n := len(s)
    pal := make([][]bool, n)
    for i := 0; i < n; i++ {
        pal[i] = make([]bool, n)
    }

    for right := 0; right < n; right++ {
        for left := 0; left <= right; left++ {
            if s[left] == s[right] && (right-left <= 2 || pal[left+1][right-1]) {
                pal[left][right] = true
            }
        }
    }

    dp := make([]int, n)
    for i := 0; i < n; i++ {
        dp[i] = i
        for j := 0; j <= i; j++ {
            if !pal[j][i] {
                continue
            }
            if j == 0 {
                dp[i] = 0
            } else if dp[j-1]+1 < dp[i] {
                dp[i] = dp[j-1] + 1
            }
        }
    }
    return dp[n-1]
}

复杂度分析

  • 时间复杂度：$O(n^2)$，回文预处理填满上三角共约 $n^2 / 2$ 个格子、每格 $O(1)$；DP 部分外层 n 次、内层最多 n 次、每次查表 $O(1)$，两段都是平方级。
  • 空间复杂度：$O(n^2)$，主要开销是 n × n 的布尔回文表，dp 数组只占 $O(n)$。

关键点总结

  • 把 DP 转移里昂贵的判定提前预处理成查表，是把 $O(n^3)$ 压到 $O(n^2)$ 的通用手法，代价是多花 $O(n^2)$ 空间。
  • 区间型递推 pal[l][r] 依赖更短的区间，枚举顺序必须保证短区间先算完；按右端点递增、左端点不超过右端点填表是最不容易出错的写法。
  • 线性 DP 的状态要定义在「前缀」上，转移时枚举最后一段的起点，这样剩余部分永远是一个已经算好的更短前缀，j == 0 也自然对应「整段不切」。
  • 求「最少切割次数」时初值取 dp[i] = i 就是天然上界（每个字符单独成段），既不用引入无穷大，也不会因为忘记初始化而出错。
  • 面试视角：131 求所有切法要用回溯，132 求最少刀数要用 DP，面试官很喜欢让你说清这条分野——枚举方案和求最优值该用不同工具；被追问空间优化时，可以谈用中心扩展一边确认回文一边更新 dp，把 $O(n^2)$ 的表省掉。

易错点总结

  • 错误写法：把状态当成「段数」，初值写 dp[i] = i + 1 且 j == 0 时置 1 → 每个答案都比正确值大 1，s = "aab" 会返回 2，正确答案是 1。
  • 错误写法：j == 0 时不特判，仍写 dp[i] = Math.min(dp[i], dp[j - 1] + 1) → 访问 dp[-1]，Java 直接数组越界，Go 同样 panic。
  • 错误写法：把 dp[i] 初始化成 0 → 初值本身就是最小可能值，任何转移都无法改进它，s = "ab" 会返回 0，正确答案是 1。
  • 错误写法：回文表的枚举写成外层 left 递增、内层 right 递增 → 算 pal[0][3] 时依赖的 pal[1][2] 还没被填过，s = "abba" 会漏判整串回文，答案变成 2，正确答案是 0。
  • 错误写法：回文条件漏掉 right - left <= 2 这一支 → pal[0][1] 会去查 pal[1][0] 这个恒为假的格子，长度为 2 的回文全部判错，s = "aa" 会返回 1，正确答案是 0。
  • 错误写法：转移写成 dp[i] = Math.min(dp[i], dp[j] + 1)，下标少减 1 → s[j] 既算进了最后一段又算进了 dp[j]，而且 j == i 时变成自我引用，s = "aab" 会返回 2，正确答案是 1。
  • 错误写法：省掉回文预处理，转移时现场用双指针判 s[j..i] 是否回文 → 单次判定退化成 $O(n)$，总复杂度升到 $O(n^3)$，n 取到 2000 时会超时。

相似题目

题目 难度 考察点
5. 最长回文子串 中等 只需回文表本身，练枚举顺序和中心扩展
131. 分割回文串 中等 要输出全部切法，用回溯而非 DP
516. 最长回文子序列 中等 对象从子串换成子序列，转移变为区间 DP
1312. 让字符串成为回文串的最少插入次数 困难 操作从切割换成插入，答案等价于长度减最长回文子序列