企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇是「算法通关手册」LeetCode 题解系列中的一篇，基于仓库内 0132. 分割回文串 II 题解 展开。题目要求将字符串分割为回文子串并返回最少分割次数，是「字符串 + 动态规划」分类下的困难题，也是线性 DP 与区间 DP 思想叠加的典型代表。读完本篇，你将掌握「回文信息预处理 + 一维线性 DP」的两阶段解法，能够独立推导状态定义、状态转移方程并写出可运行的 Python 实现，同时理解它与姊妹题「分割回文串 I」在解题范式上的本质差异。

一、题目解读：从「输出所有方案」到「求最少次数」

给定一个字符串s，要求将其分割成若干子串，使每个子串都是回文串，返回符合要求的最少分割次数。

• 输入：字符串s，仅由小写英文字母组成，长度1 ≤ s.length ≤ 2000；
• 输出：整数，即最少分割次数；
• 示例 1：s = "aab"，输出1。因为只需 1 次分割即可得到["aa", "b"]两个回文子串；
• 示例 2：s = "a"，输出0。单个字符本身就是回文串，无需分割。

注意「分割次数」与「回文子串个数」的关系：若s被分成k段回文子串，则分割次数为k - 1。例如"aab"分成 2 段，分割次数为 1。

数据规模n ≤ 2000提示我们：$O(n^2)$ 时间复杂度的算法是可行的，而 $O(n^3)$ 的暴力做法会超时，这为后面的动态规划解法划定了设计空间。

二、为什么不能直接套用「分割回文串 I」的回溯

仓库中还有一道姊妹题 0131. 分割回文串，它要求返回所有可行的分割方案，标准做法是回溯 + 回文判断（见其题解中backtrack与ispalindrome的实现）。

两道题虽然共享「回文子串」的概念，但目标完全不同：

本题只需最少数值，无需枚举全部方案，因此用动态规划既正确又高效。这与仓库 08_03_linear_dp_01.md 中「单串线性 DP」的定位完全吻合——输入是单个字符串，状态按前缀位置线性划分。

三、解题思路：两阶段动态规划

3.1 核心思想总览

直接求最少分割次数时，我们面临一个子问题：前缀s[0..i]的最少分割次数是多少？它只与更短前缀的最优解相关，天然具有「最优子结构」，适合动态规划。

整个解法分为两个阶段：

1. 回文信息预处理：预先判定所有子串s[i..j]是否为回文，记为is_palindrome[i][j]；
2. 最少分割次数 DP：从左到右计算每个前缀的最少分割次数dp[i]。

第二阶段在状态转移时要用到第一阶段的结果。这正是仓库 08_11_interval_dp.md 中「单区间扩展型」区间 DP 思想的体现：s[i..j]是否为回文，可由内层子区间s[i+1..j-1]加上首尾字符是否相等递推得到。

3.2 阶段一：回文子串的区间 DP 预处理

回文的判定具有递归结构：

• 长度为 1：任何单个字符s[i]都是回文，即is_palindrome[i][i] = True；
• 长度为 2：s[i]与s[i+1]相等时是回文，即is_palindrome[i][i+1] = (s[i] == s[i+1])；
• 长度 ≥ 3：s[i..j]是回文当且仅当首尾字符相等且去掉首尾后的内部子串s[i+1..j-1]是回文，即：

$$is_palindrome[i][j] = (s[i] == s[j]) \land is_palindrome[i+1][j-1]$$

因此，只需按照区间长度从小到大枚举（保证计算长区间时内部短区间已被填好），即可在 $O(n^2)$ 时间内填满整张is_palindrome二维表。

3.3 阶段二：最少分割次数的一维线性 DP

状态定义：dp[i]表示前缀s[0..i]的最少分割次数。

初始化：最坏情况下每个字符都单独成段，即把s[0..i]分成i + 1段，需要i次分割，所以初始令dp[i] = i。

状态转移：考察以位置i结尾的所有回文子串s[j..i]（其中0 ≤ j ≤ i）：

• 若j == 0且s[0..i]本身就是回文，则整个前缀无需分割，dp[i] = 0；
• 否则，若s[j..i]是回文，说明在位置j - 1处切一刀后，前缀s[0..j-1]与回文段s[j..i]各自独立，于是：

$$dp[i] = \min(dp[i],\ dp[j-1] + 1),\quad 1 \le j \le i \text{ 且 } s[j..i] \text{ 是回文}$$

最终答案：dp[n - 1]，即整个字符串的最少分割次数。

这个转移模式与仓库中另一道单串 DP 题 0139. 单词拆分 高度相似：二者都是「枚举最后一个合法段 + 使用前缀状态」的经典结构，区别仅在于本题的合法段判定依据是回文表，而单词拆分依据的是字典。

四、完整代码实现（Python）

以下代码完整取自原题解（palindrome-partitioning-ii.md），可直接提交运行：

class Solution: def minCut(self, s: str) -> int: n = len(s) # 预处理：判断所有子串是否为回文 is_palindrome = [[False] * n for _ in range(n)] # 单个字符都是回文 for i in range(n): is_palindrome[i][i] = True # 两个相邻字符 for i in range(n - 1): is_palindrome[i][i + 1] = (s[i] == s[i + 1]) # 长度大于2的子串 for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 is_palindrome[i][j] = (s[i] == s[j]) and is_palindrome[i + 1][j - 1] # 动态规划求解最少分割次数 dp = [0] * n for i in range(n): # 最坏情况：每个字符都单独分割 dp[i] = i # 如果整个子串是回文，不需要分割 if is_palindrome[0][i]: dp[i] = 0 else: # 尝试所有可能的分割点 for j in range(1, i + 1): if is_palindrome[j][i]: dp[i] = min(dp[i], dp[j - 1] + 1) return dp[n - 1]

4.1 代码逐段说明

第 1 段（预处理初始化）：构造n × n的布尔表，先填两种平凡情形——对角线上的单字符子串恒为回文；相邻字符子串是否回文取决于两字符是否相等。

第 2 段（区间长度递推）：从长度 3 开始枚举length，对每个起点i求出右端点j = i + length - 1。转移时只需比较s[i]、s[j]并读取内层is_palindrome[i + 1][j - 1]，无需重新扫描整个子串，这正是预处理的意义——把后续阶段的回文判断降为 $O(1)$ 查询。

第 3 段（线性 DP）：对每个位置i先赋最坏值i。若is_palindrome[0][i]为真，说明前缀整体回文，直接置 0；否则遍历j ∈ [1, i]，凡是以i结尾的回文子串s[j..i]，都用「前缀s[0..j-1]的最少分割次数 + 1（在j - 1处切一刀）」尝试更新dp[i]。注意j从 1 开始枚举，避免了与is_palindrome[0][i]分支的重复判断。

4.2 本地验证

如需在本地（如 codes 目录之外的任意 Python 3 环境）验证，可补一段驱动代码：

if __name__ == "__main__": solver = Solution() print(solver.minCut("aab")) # 期望输出 1 print(solver.minCut("a")) # 期望输出 0 print(solver.minCut("ab")) # 期望输出 1 print(solver.minCut("aa")) # 期望输出 0

五、复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是字符串长度。预处理回文表：外层枚举区间长度 $O(n)$，内层枚举起点 $O(n)$，合计 $O(n^2)$；最少分割次数的 DP：外层枚举i为 $O(n)$，内层枚举j为 $O(n)$，合计 $O(n^2)$。两阶段相加仍为 $O(n^2)$。
• 空间复杂度：$O(n^2)$。is_palindrome二维布尔表占用 $O(n^2)$，dp一维数组占用 $O(n)$，取最大值即 $O(n^2)$。

在n ≤ 2000的约束下，$O(n^2)$ 的时间与空间都是可接受的。

六、边界情况与正确性推敲

• 单字符字符串：dp[0] = 0，is_palindrome[0][0] = True，直接返回 0，无需分割。
• 整串本身就是回文：如"aa"、"aba"，is_palindrome[0][i]为真，dp[i] = 0，答案为 0。
• 不存在任何长度 ≥ 2 的回文子串：如"ab"，dp[1]只能由s[1..1] = "b"转移，即dp[0] + 1 = 1，符合预期。
• 手工推演"aab"：
  • 预处理："aa"是回文，"ab"不是，"aab"不是；
  • dp[0] = 0（"a"是回文）；
  • dp[1] = 1（"aa"是回文，dp[1] = 0才对）——等等，is_palindrome[0][1]为真，所以dp[1] = 0；
  • dp[2]：s[0..2] = "aab"非回文，考察j = 1：s[1..2] = "ab"非回文；j = 2：s[2..2] = "b"是回文，dp[2] = min(2, dp[1] + 1) = min(2, 0 + 1) = 1。
  • 最终答案 1，与题目示例一致。

七、思路延伸：等价的中心扩展预处理与空间优化方向

从源码结构看，原题解采用的预处理是「区间长度递推」写法。除此之外，还存在两种常见的等价或优化做法，可作为面试延伸：

1. 中心扩展法预处理：以每个字符（奇数长度回文中心）和每对相邻字符（偶数长度回文中心）为起点向两侧扩展，同样能在 $O(n^2)$ 时间内填好回文表。它省去了长度循环，在某些实现中更直观，但时间复杂度量级不变。
2. 空间维度压缩：dp转移只关心「以i结尾的回文子串的左端点集合」。可以只在第二层 DP 过程中动态维护这些左端点，或将is_palindrome按行/按需存储，从而把空间从 $O(n^2)$ 进一步压低。这类优化需要额外小心边界处理，属于进阶话题。

无论采用哪种预处理写法，两阶段 DP 的整体框架不变，这也是本题最值得掌握的核心。

八、相关题目与本仓库学习路径

围绕「回文 + 动态规划」这条主线，本仓库提供了完整的学习链路，建议按序阅读：

• 字符串基础：回文串属于字符串问题五大分类之一，见 04_01_string_basic.md；
• 线性 DP 入门：理解单串线性 DP 的三种状态定义方式，见 08_03_linear_dp_01.md；
• 区间 DP 原理：本题回文预处理的递推结构来自「单区间扩展型」区间 DP，见 08_11_interval_dp.md；
• 姊妹题对比：0131 分割回文串（回溯求全部方案），见 palindrome-partitioning.md；
• 同构 DP 模式：0139 单词拆分（同样按最后一段 + 前缀状态转移），见 word-break.md；
• 回文系列巩固：0005 最长回文子串（longest-palindromic-substring.md）、0516 最长回文子序列（longest-palindromic-subsequence.md）、1278 分割回文串 III（palindrome-partitioning-iii.md）。

完整的题目分类索引可参考 00_06_categories_list.md，本题在「字符串」「动态规划」两个分类下均有收录。

九、小结

LeetCode 0132「分割回文串 II」的解题要点可浓缩为三点：

1. 先预处理回文表，用区间 DP 的递推关系在 $O(n^2)$ 内回答所有「子串是否回文」的查询；
2. 再跑一维线性 DP，以dp[i]表示前缀s[0..i]的最少分割次数，转移时枚举以i结尾的回文段，套用dp[i] = min(dp[i], dp[j-1] + 1)；
3. 整体复杂度 $O(n^2)$，在n ≤ 2000的数据范围内运行高效，也是面试中考察「回文 + 动态规划」组合能力的标准题型。

掌握「两阶段 DP」这一范式后，无论是回文分割、单词拆分还是其他「段划分 + 前缀最优」类问题，都能快速迁移求解。

• 教程
• 文档
• 知识库