132 分割回文串Ⅱ

一、题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

二、题解

思路：两次动态规划 一次用来预处理所有的回文子串，另一次用来计算最少的分割次数。

第一步：预处理回文串（二维 DP） 如果我们在计算分割次数时，每次都去用双指针判断某个子串是不是回文串，会非常耗时。我们可以先用一个二维数组 isPal[i][j] 记录下来：字符串 s 从索引 i 到 j 的子串是否是回文串。

• 状态转移： 如果 s[i] == s[j]，并且它们中间包含的子串 s[i+1...j-1] 也是回文串，那么 s[i...j] 就是回文串。
• 即：isPal[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i <= 2 || isPal[i + 1][j - 1])。

第二步：计算最少分割次数（一维 DP）

• 状态定义： 定义 dp[i] 表示字符串的前缀 s[0...i] 分割成若干个回文子串所需要的最少分割次数。
• 初始状态： 最坏的情况下，长度为 i + 1 的字符串需要分割 i 次（每个字符单独成一个回文串），所以 dp[i] 初始为 i。
• 状态转移：
  1. 如果整个前缀 s[0...i] 本身就是一个回文串（查表 isPal[0][i]），那么根本不需要分割，dp[i] = 0。
  2. 如果不是，我们就尝试在 0 到 i 之间寻找一个切割点 j（$1 \le j \le i$）。如果后缀 s[j...i] 是一个回文串，那么我们就可以在 j-1 和 j 之间切一刀。此时的分割次数就是前缀 s[0...j-1] 的最少分割次数加上这新的一刀。
  3. 即：dp[i] = Math.min(dp[i], dp[j - 1] + 1)，前提是 isPal[j][i] == true。

class Solution {
    public int minCut(String s) {
        int n = s.length();
        if (n <= 1) return 0;

        // 第一步：预处理所有的回文子串
        boolean[][] isPal = new boolean[n][n];
        // 注意遍历顺序：i 从大到小，j 从小到大，保证计算 isPal[i][j] 时，isPal[i+1][j-1] 已经计算过了
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || isPal[i + 1][j - 1])) {
                    isPal[i][j] = true;
                }
            }
        }

        // 第二步：动态规划计算最少分割次数
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            // 初始值：最坏情况下，s[0...i] 需要切 i 刀（全切成单个字符）
            dp[i] = i;
        }

        for (int i = 1; i < n; i++) {
            // 如果 s[0...i] 整体是回文串，一刀都不用切
            if (isPal[0][i]) {
                dp[i] = 0;
                continue;
            }

            // 尝试在 j 的前面切一刀，枚举所有的 j
            for (int j = 1; j <= i; j++) {
                // 只有当后半部分 s[j...i] 是回文串时，这一刀切得才有意义
                if (isPal[j][i]) {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }

        // 返回整个字符串 s[0...n-1] 的最少分割次数
        return dp[n - 1];
    }
}

时间复杂度：$O(n^2)$

空间复杂度：$O(n^2)$