分割回文串 II 如何用动态规划求最少切割次数？为什么要先预处理回文？

简化版

分割回文串 II 先用 DP 预处理 isPal[i][j] 表示子串 s[i..j] 是否为回文，再用 cut[i] 表示前缀 s[0..i] 的最少切割次数。若 s[0..i] 是回文，cut[i]=0；否则枚举切点 j，用 cut[j-1]+1 更新。

详细版

直接枚举所有切法会指数爆炸。优化思路是把“判断某段是不是回文”提前做成表，之后每次查询 O(1)。回文表转移为：s[i] == s[j] 且内部 s[i+1..j-1] 是回文，长度小于 3 时只要两端相等即可。

最少切割 DP 中，cut[i] 表示 s[0..i] 最少切几刀能让每段都是回文。时间复杂度 O(n²)，空间复杂度 O(n²)，主要花在回文预处理表上。

完整版教学

一、这题和分割回文串 I 的区别

分割回文串 I 通常要求返回所有方案，适合回溯。分割回文串 II 只问最少切割次数，目标从“枚举所有结果”变成“求最优值”，这就是动态规划的信号。

s = "aab"
可分割：
["a","a","b"] 切 2 刀
["aa","b"]    切 1 刀
答案：1

如果继续用回溯枚举所有方案，再取最小，会在长字符串上非常慢。

二、为什么要先预处理回文表

最少切割过程中会反复问：s[j..i] 是不是回文。如果每次都双指针检查，单次 O(n)，外层再枚举切点，整体可能到 O(n³)。

预处理表：

isPal[i][j] = s[i..j] 是否为回文

查询时就变成 O(1)。这是典型的“用空间换时间”：多用 O(n²) 空间，换掉大量重复判断。

记忆钩子：这题先把“某段是不是回文”变成常量时间查询，再讨论“在哪里切最少”，顺序不要反。

三、回文表的转移怎么写

一个子串是回文，需要两端字符相等，并且中间也是回文：

isPal[i][j] = s[i] == s[j] && (j - i < 2 || isPal[i + 1][j - 1])

其中 j-i<2 覆盖长度 1 和长度 2：

子串长度	条件
1	单字符一定回文
2	两端相等就是回文
>=3	两端相等且内部回文

填表时 i 要从后往前，j 从 i 往后，这样 isPal[i+1][j-1] 已经算好。

四、最少切割状态怎么定义

定义：

cut[i] = s[0..i] 被切成若干回文子串所需的最少切割次数

如果 s[0..i] 自己就是回文，则不需要切：

cut[i] = 0

否则枚举最后一段的起点 j，如果 s[j..i] 是回文，那么前面 s[0..j-1] 的答案是 cut[j-1]，再切一刀连接最后一段：

cut[i] = min(cut[i], cut[j - 1] + 1)

五、用 aab 走一遍

s="aab"：

isPal[0][0] = true  // "a"
isPal[1][1] = true  // "a"
isPal[2][2] = true  // "b"
isPal[0][1] = true  // "aa"

计算 cut：

cut[0] = 0      // "a"
cut[1] = 0      // "aa"
cut[2] = cut[1] + 1 = 1，因为最后一段 "b" 是回文

答案是 1，对应 "aa" | "b"。

六、代码模板

int minCut(String s) {
    int n = s.length();
    boolean[][] isPal = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            isPal[i][j] = s.charAt(i) == s.charAt(j)
                && (j - i < 2 || isPal[i + 1][j - 1]);
        }
    }
    int[] cut = new int[n];
    Arrays.fill(cut, n);
    for (int i = 0; i < n; i++) {
        if (isPal[0][i]) {
            cut[i] = 0;
        } else {
            for (int j = 1; j <= i; j++) {
                if (isPal[j][i]) cut[i] = Math.min(cut[i], cut[j - 1] + 1);
            }
        }
    }
    return cut[n - 1];
}

j 从 1 开始，是因为 j=0 的情况已经由 isPal[0][i] 单独处理，否则会访问 cut[-1]。

七、常见误区与追问

误区：每次判断回文都重新扫描。 会把复杂度推高到 O(n³)。
误区：把段数当切割次数返回。 段数比切割次数多 1。
误区：回文表填表方向错误。 isPal[i][j] 依赖 isPal[i+1][j-1]，所以 i 要倒序。
追问：为什么 s[0..i] 是回文时切 0 刀？ 整个前缀已经是一段回文，不需要切分。
追问：空间能否优化？ 回文表较难完全省掉，也可以用中心扩展结合切割数组优化思路。
追问：和回溯枚举有什么关系？ 回溯求所有方案，DP 求最少切割，是目标不同导致方法不同。

八、加强记忆

分割回文串 II 是“两层 DP”：先把回文判断做成 isPal 表，再用 cut 求最少切割。cut[i] 问前缀最少切几刀，最后一段如果是回文，就从切点前的答案加一刀。记住段数和切割次数差 1，s[0..i] 本身回文时答案是 0。

简化版

详细版