教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇是「算法通关手册」LeetCode 题解系列中的一篇基于仓库内 0132. 分割回文串 II 题解 展开。题目要求将字符串分割为回文子串并返回最少分割次数是「字符串 动态规划」分类下的困难题也是线性 DP 与区间 DP 思想叠加的典型代表。读完本篇你将掌握「回文信息预处理 一维线性 DP」的两阶段解法能够独立推导状态定义、状态转移方程并写出可运行的 Python 实现同时理解它与姊妹题「分割回文串 I」在解题范式上的本质差异。一、题目解读从「输出所有方案」到「求最少次数」给定一个字符串s要求将其分割成若干子串使每个子串都是回文串返回符合要求的最少分割次数。输入字符串s仅由小写英文字母组成长度1 ≤ s.length ≤ 2000输出整数即最少分割次数示例 1s aab输出1。因为只需 1 次分割即可得到[aa, b]两个回文子串示例 2s a输出0。单个字符本身就是回文串无需分割。注意「分割次数」与「回文子串个数」的关系若s被分成k段回文子串则分割次数为k - 1。例如aab分成 2 段分割次数为 1。数据规模n ≤ 2000提示我们$O(n^2)$ 时间复杂度的算法是可行的而 $O(n^3)$ 的暴力做法会超时这为后面的动态规划解法划定了设计空间。二、为什么不能直接套用「分割回文串 I」的回溯仓库中还有一道姊妹题 0131. 分割回文串它要求返回所有可行的分割方案标准做法是回溯 回文判断见其题解中backtrack与ispalindrome的实现。两道题虽然共享「回文子串」的概念但目标完全不同维度0131 分割回文串0132 分割回文串 II求什么所有分割方案回溯枚举最少分割次数最优化算法范式回溯 / DFS动态规划搜索空间可能呈指数级多项式可解难点枚举 剪枝状态设计与转移本题只需最少数值无需枚举全部方案因此用动态规划既正确又高效。这与仓库 08_03_linear_dp_01.md 中「单串线性 DP」的定位完全吻合——输入是单个字符串状态按前缀位置线性划分。三、解题思路两阶段动态规划3.1 核心思想总览直接求最少分割次数时我们面临一个子问题前缀s[0..i]的最少分割次数是多少它只与更短前缀的最优解相关天然具有「最优子结构」适合动态规划。整个解法分为两个阶段回文信息预处理预先判定所有子串s[i..j]是否为回文记为is_palindrome[i][j]最少分割次数 DP从左到右计算每个前缀的最少分割次数dp[i]。第二阶段在状态转移时要用到第一阶段的结果。这正是仓库 08_11_interval_dp.md 中「单区间扩展型」区间 DP 思想的体现s[i..j]是否为回文可由内层子区间s[i1..j-1]加上首尾字符是否相等递推得到。3.2 阶段一回文子串的区间 DP 预处理回文的判定具有递归结构长度为 1任何单个字符s[i]都是回文即is_palindrome[i][i] True长度为 2s[i]与s[i1]相等时是回文即is_palindrome[i][i1] (s[i] s[i1])长度 ≥ 3s[i..j]是回文当且仅当首尾字符相等且去掉首尾后的内部子串s[i1..j-1]是回文即$$is_palindrome[i][j] (s[i] s[j]) \land is_palindrome[i1][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] 0is_palindrome[0][0] True直接返回 0无需分割。整串本身就是回文如aa、abais_palindrome[0][i]为真dp[i] 0答案为 0。不存在任何长度 ≥ 2 的回文子串如abdp[1]只能由s[1..1] b转移即dp[0] 1 1符合预期。手工推演aab预处理aa是回文ab不是aab不是dp[0] 0a是回文dp[1] 1aa是回文dp[1] 0才对——等等is_palindrome[0][1]为真所以dp[1] 0dp[2]s[0..2] aab非回文考察j 1s[1..2] ab非回文j 2s[2..2] b是回文dp[2] min(2, dp[1] 1) min(2, 0 1) 1。最终答案 1与题目示例一致。七、思路延伸等价的中心扩展预处理与空间优化方向从源码结构看原题解采用的预处理是「区间长度递推」写法。除此之外还存在两种常见的等价或优化做法可作为面试延伸中心扩展法预处理以每个字符奇数长度回文中心和每对相邻字符偶数长度回文中心为起点向两侧扩展同样能在 $O(n^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 分割回文串 IIIpalindrome-partitioning-iii.md。完整的题目分类索引可参考 00_06_categories_list.md本题在「字符串」「动态规划」两个分类下均有收录。九、小结LeetCode 0132「分割回文串 II」的解题要点可浓缩为三点先预处理回文表用区间 DP 的递推关系在 $O(n^2)$ 内回答所有「子串是否回文」的查询再跑一维线性 DP以dp[i]表示前缀s[0..i]的最少分割次数转移时枚举以i结尾的回文段套用dp[i] min(dp[i], dp[j-1] 1)整体复杂度 $O(n^2)$在n ≤ 2000的数据范围内运行高效也是面试中考察「回文 动态规划」组合能力的标准题型。掌握「两阶段 DP」这一范式后无论是回文分割、单词拆分还是其他「段划分 前缀最优」类问题都能快速迁移求解。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 132. 分割回文串 II 最小分割次数详解回文预处理 动态规划实战LeetCode 132. 分割回文串 II 最小分割次数详解回文预处理 动态规划实战 本文以 LeetCode 132「分割回文串 II」Palind文档教程知识库分割回文串回溯法与动态规划的预处理分割回文串回溯法与动态规划的预处理 在LeetCode算法题中分割回文串是一个经典的字符串处理问题它要求将一个字符串分割成若干个子串使每个子串都是回示例工程教程LeetCode 131. 分割回文串回溯法求解所有分割方案的完整实战解析LeetCode 131. 分割回文串回溯法求解所有分割方案的完整实战解析 导读 131. 分割回文串 https://link.gitcode.com/i/文档教程知识库上一篇OHIF 3.9 ViewportActionCornersService 迁移指南用 addComponent / addComponents 实现可靠的视口角落组件定位下一篇MiroFish智能体通信系统从架构设计到实践落地创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 算法通关手册 · LeetCode 0132「分割回文串 II」：回文子串预处理 + 单串线性 DP 求最少分割次数
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇是「算法通关手册」LeetCode 题解系列中的一篇基于仓库内 0132. 分割回文串 II 题解 展开。题目要求将字符串分割为回文子串并返回最少分割次数是「字符串 动态规划」分类下的困难题也是线性 DP 与区间 DP 思想叠加的典型代表。读完本篇你将掌握「回文信息预处理 一维线性 DP」的两阶段解法能够独立推导状态定义、状态转移方程并写出可运行的 Python 实现同时理解它与姊妹题「分割回文串 I」在解题范式上的本质差异。一、题目解读从「输出所有方案」到「求最少次数」给定一个字符串s要求将其分割成若干子串使每个子串都是回文串返回符合要求的最少分割次数。输入字符串s仅由小写英文字母组成长度1 ≤ s.length ≤ 2000输出整数即最少分割次数示例 1s aab输出1。因为只需 1 次分割即可得到[aa, b]两个回文子串示例 2s a输出0。单个字符本身就是回文串无需分割。注意「分割次数」与「回文子串个数」的关系若s被分成k段回文子串则分割次数为k - 1。例如aab分成 2 段分割次数为 1。数据规模n ≤ 2000提示我们$O(n^2)$ 时间复杂度的算法是可行的而 $O(n^3)$ 的暴力做法会超时这为后面的动态规划解法划定了设计空间。二、为什么不能直接套用「分割回文串 I」的回溯仓库中还有一道姊妹题 0131. 分割回文串它要求返回所有可行的分割方案标准做法是回溯 回文判断见其题解中backtrack与ispalindrome的实现。两道题虽然共享「回文子串」的概念但目标完全不同维度0131 分割回文串0132 分割回文串 II求什么所有分割方案回溯枚举最少分割次数最优化算法范式回溯 / DFS动态规划搜索空间可能呈指数级多项式可解难点枚举 剪枝状态设计与转移本题只需最少数值无需枚举全部方案因此用动态规划既正确又高效。这与仓库 08_03_linear_dp_01.md 中「单串线性 DP」的定位完全吻合——输入是单个字符串状态按前缀位置线性划分。三、解题思路两阶段动态规划3.1 核心思想总览直接求最少分割次数时我们面临一个子问题前缀s[0..i]的最少分割次数是多少它只与更短前缀的最优解相关天然具有「最优子结构」适合动态规划。整个解法分为两个阶段回文信息预处理预先判定所有子串s[i..j]是否为回文记为is_palindrome[i][j]最少分割次数 DP从左到右计算每个前缀的最少分割次数dp[i]。第二阶段在状态转移时要用到第一阶段的结果。这正是仓库 08_11_interval_dp.md 中「单区间扩展型」区间 DP 思想的体现s[i..j]是否为回文可由内层子区间s[i1..j-1]加上首尾字符是否相等递推得到。3.2 阶段一回文子串的区间 DP 预处理回文的判定具有递归结构长度为 1任何单个字符s[i]都是回文即is_palindrome[i][i] True长度为 2s[i]与s[i1]相等时是回文即is_palindrome[i][i1] (s[i] s[i1])长度 ≥ 3s[i..j]是回文当且仅当首尾字符相等且去掉首尾后的内部子串s[i1..j-1]是回文即$$is_palindrome[i][j] (s[i] s[j]) \land is_palindrome[i1][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] 0is_palindrome[0][0] True直接返回 0无需分割。整串本身就是回文如aa、abais_palindrome[0][i]为真dp[i] 0答案为 0。不存在任何长度 ≥ 2 的回文子串如abdp[1]只能由s[1..1] b转移即dp[0] 1 1符合预期。手工推演aab预处理aa是回文ab不是aab不是dp[0] 0a是回文dp[1] 1aa是回文dp[1] 0才对——等等is_palindrome[0][1]为真所以dp[1] 0dp[2]s[0..2] aab非回文考察j 1s[1..2] ab非回文j 2s[2..2] b是回文dp[2] min(2, dp[1] 1) min(2, 0 1) 1。最终答案 1与题目示例一致。七、思路延伸等价的中心扩展预处理与空间优化方向从源码结构看原题解采用的预处理是「区间长度递推」写法。除此之外还存在两种常见的等价或优化做法可作为面试延伸中心扩展法预处理以每个字符奇数长度回文中心和每对相邻字符偶数长度回文中心为起点向两侧扩展同样能在 $O(n^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 分割回文串 IIIpalindrome-partitioning-iii.md。完整的题目分类索引可参考 00_06_categories_list.md本题在「字符串」「动态规划」两个分类下均有收录。九、小结LeetCode 0132「分割回文串 II」的解题要点可浓缩为三点先预处理回文表用区间 DP 的递推关系在 $O(n^2)$ 内回答所有「子串是否回文」的查询再跑一维线性 DP以dp[i]表示前缀s[0..i]的最少分割次数转移时枚举以i结尾的回文段套用dp[i] min(dp[i], dp[j-1] 1)整体复杂度 $O(n^2)$在n ≤ 2000的数据范围内运行高效也是面试中考察「回文 动态规划」组合能力的标准题型。掌握「两阶段 DP」这一范式后无论是回文分割、单词拆分还是其他「段划分 前缀最优」类问题都能快速迁移求解。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 132. 分割回文串 II 最小分割次数详解回文预处理 动态规划实战LeetCode 132. 分割回文串 II 最小分割次数详解回文预处理 动态规划实战 本文以 LeetCode 132「分割回文串 II」Palind文档教程知识库分割回文串回溯法与动态规划的预处理分割回文串回溯法与动态规划的预处理 在LeetCode算法题中分割回文串是一个经典的字符串处理问题它要求将一个字符串分割成若干个子串使每个子串都是回示例工程教程LeetCode 131. 分割回文串回溯法求解所有分割方案的完整实战解析LeetCode 131. 分割回文串回溯法求解所有分割方案的完整实战解析 导读 131. 分割回文串 https://link.gitcode.com/i/文档教程知识库上一篇OHIF 3.9 ViewportActionCornersService 迁移指南用 addComponent / addComponents 实现可靠的视口角落组件定位下一篇MiroFish智能体通信系统从架构设计到实践落地创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考