分割回文串 II 图解题解

分割回文串 II 到底在求什么

给字符串 s，切成若干段、每段都是回文串（正反读一样，如 "aa"、"aba"），问最少切几刀（切 k 刀得 k+1 段）、即刀数的最小值。题面 s="aab" 切 1 刀成 "aa" 和 "b"；s="a" 本身回文，0 刀。

为什么把每种切法都试一遍会爆

长度 n 的串，相邻字符间每处都可切可不切，共 2ⁿ⁻¹ 种切法。n 才二十出头就几十万条，指数增长把逐条枚举压垮。

就算改成往前递归，也躲不开同一子串被反复验证是不是回文，而判一次回文最坏要扫半个串、是 O(n)。叠一起就没法用。

判一段是不是回文，怎么压成一步

先省掉反复判回文。一个串是回文靠两条：首尾字符相等，且去掉首尾的里层也回文。"abcba" 就因首尾 'a' 相等、里层 "bcb" 也回文。大回文踩着里层小回文层层搭起来，这就是区间 DP（长区间直接查短区间算好的结果、不重算）。

开回文表 pal，pal[j][i] 记「s 第 j 到第 i 位是否回文」（下标从 0 数起）：s[j] 与 s[i] 相等、且里层 pal[j+1][i−1] 已为真时成立；段长不超过 3 时里层至多一字符、天然回文，首尾一等即可。里层更早填好，查一步就是 O(1)，判回文从 O(n) 降下来。

dp[i] 怎么由更短的 dp 拼出来

回文能一步判就算刀数。定义 dp[i] 为「s 前 i+1 位最少切几刀」，算过的往下记、不重算。

算 dp[i] 时，最后一段右端固定在第 i 位、左端记作第 j 位。s[j..i] 回文（查表即知）时它不用切，前面「s 前 j 位」是更短子问题、答案 dp[j−1]，加 1 刀得 dp[j−1]+1。让 s[j..i] 回文的 j 取最小就是 dp[i]，这叫转移。

左端 j 落在第 0 位时整段前缀 s[0..i] 自己就回文、0 刀，dp[i] 直接是 0。dp[i] 起手设成 i 兜底，是「每字符各切一刀」的上界，会被更省方案压掉。

拿 aab 亲手把回文表和 dp 填一遍

串 "aab" 三字符，从左到右来。头一位 'a' 单字符回文，前缀 "a" 的 dp 记 0。第二位 'a'："aa" 首尾都 'a'、段长 2 成立，整段回文，dp 记 0。

末一位 'b'：往左试，"aab"、"ab" 首尾都不等，只有 "b" 单字符回文。最后一段 "b"，前面 "aa" 的 dp 记着 0，加一刀得 1。dp 末格 1 就是答案：切 1 刀成 "aa" 和 "b"，对上题面。

短段特判和 dp 初值，哪个先崩

外层每个右端、内层枚举左端都是 O(n)，查表判回文 O(1)，时间 O(n²)。回文表 n×n 占 O(n²)、dp 只 O(n)，主导 O(n²)；改用「中心扩展」逐中心外扩，空间可压到 O(n)。

短段特判漏了最伤：段长不超过 3 本该首尾等就成立，漏了会去查里层 pal[j+1][i−1] 的假值、把长回文漏判。dp 初值也别写 0，得是 i 这个「全切单字符」的上界，写小了会混进假刀数。整段本就回文时答案 0、凑不出长回文时 n−1。

Python

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        pal = [[False] * n for _ in range(n)]
        dp = [0] * n
        for i in range(n):
            best = i
            for j in range(i + 1):
                if s[j] == s[i] and (i - j <= 2 or pal[j + 1][i - 1]):
                    pal[j][i] = True
                    best = 0 if j == 0 else min(best, dp[j - 1] + 1)
            dp[i] = best
        return dp[-1]

C++

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<int>> pal(n, vector<int>(n));
        vector<int> dp(n);
        for (int i = 0; i < n; ++i) {
            int best = i;
            for (int j = 0; j <= i; ++j) if (s[j] == s[i] && (i - j <= 2 || pal[j+1][i-1])) {
                pal[j][i] = 1;
                best = j == 0 ? 0 : min(best, dp[j-1] + 1);
            }
            dp[i] = best;
        }
        return dp.back();
    }
};

Java

import java.util.*;
class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] pal = new boolean[n][n];
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            int best = i;
            for (int j = 0; j <= i; j++) if (s.charAt(j) == s.charAt(i) && (i - j <= 2 || pal[j + 1][i - 1])) {
                pal[j][i] = true;
                best = j == 0 ? 0 : Math.min(best, dp[j - 1] + 1);
            }
            dp[i] = best;
        }
        return dp[n - 1];
    }
}