题目描述
思路解析
一句话答案：LeetCode 132 分割回文串 II 求把串切成若干回文段的最少刀数。两层动态规划：先用回文表（每段回不回文先记好）O(1) 判回文，再让 dp[i] 记前 i+1 位最少切割、由更短的 dp 转移。时空 O(n²)。
分割回文串 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。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「枚举最后一段的左端 j,若 s[j..i] 回文就用 dp[j−1]+1 更新 dp[i]」,下面逐位套它。
演示串 banana。右端先固定在 i=0（字符 'b'），把它当作最后一段的结尾；dp[0] 初值设为最坏情况 0——单字符前缀最多切 0 刀。
试左端 j=0：子串 "b" 单字符必是回文，且 j=0 说明整个前缀本身就是一段回文，dp[0] 直接置 0，一刀都不用切。
右端 i=0 的所有左端都试完，定下 dp[0]=0：前缀 "b" 最少切 0 刀。
右端来到 i=1（字符 'a'）：dp[1] 初值设为最坏情况 1——把 "ba" 切成两个单字符要 1 刀。
试左端 j=0：子串 s[0..1]="ba" 首尾 'b'≠'a'，不是回文，跳过这个切法。
试左端 j=1：末段 "a" 是回文 → 候选 dp[0]+1=1，不比当前 dp[1]=1 更小，保持 1。
右端 i=1 试完，定下 dp[1]=1：前缀 "ba" 最少切 1 刀。
右端来到 i=2（字符 'n'）：dp[2] 初值设为最坏情况 2（三个单字符切 2 刀）。
试左端 j=0：子串 "ban" 首尾 'b'≠'n'，不是回文，跳过。
试左端 j=1：子串 "an" 首尾 'a'≠'n'，不是回文，跳过。
试左端 j=2：末段 "n" 是回文 → 候选 dp[1]+1=2，与初值持平，dp[2] 保持 2。
右端 i=2 试完，定下 dp[2]=2：前缀 "ban" 只能切成三个单字符。
右端来到 i=3（字符 'a'）：dp[3] 初值设为最坏情况 3。
试左端 j=0：子串 "bana" 首尾 'b'≠'a'，不是回文，跳过。
试左端 j=1：末段 "ana" 是回文！前面只剩 "b"：候选 dp[0]+1=1，比 3 小得多，更新 dp[3]=1。
试左端 j=2：子串 "na" 首尾不等，不是回文，跳过。
试左端 j=3：末段 "a" 是回文 → 候选 dp[2]+1=3，不如现在的 1，保持 dp[3]=1。
右端 i=3 试完，定下 dp[3]=1：前缀 "bana" 最优切法是 b | ana。
右端来到 i=4（字符 'n'）：dp[4] 初值设为最坏情况 4。
试左端 j=0：子串 "banan" 首尾 'b'≠'n'，不是回文，跳过。
试左端 j=1：子串 "anan" 首尾 'a'≠'n'，不是回文，跳过。
试左端 j=2：末段 "nan" 是回文 → 候选 dp[1]+1=2，比 4 小，更新 dp[4]=2。
试左端 j=3：子串 "an" 首尾不等，不是回文，跳过。
试左端 j=4：末段 "n" 是回文 → 候选 dp[3]+1=2，与当前 2 持平，保持。
右端 i=4 试完，定下 dp[4]=2：前缀 "banan" 最少切 2 刀（如 b | a | nan）。
右端来到最后一位 i=5（字符 'a'）：dp[5] 初值设为最坏情况 5。
试左端 j=0：整串 "banana" 首尾 'b'≠'a'，不是回文，跳过。
试左端 j=1：末段 "anana" 是回文！前面只剩 "b"：候选 dp[0]+1=1，大幅变小，更新 dp[5]=1。
试左端 j=2：子串 "nana" 首尾 'n'≠'a'，不是回文，跳过。
试左端 j=3：末段 "ana" 是回文 → 候选 dp[2]+1=3，不如 1，保持。
试左端 j=4：子串 "na" 首尾不等，不是回文，跳过。
试左端 j=5：末段 "a" 是回文 → 候选 dp[4]+1=3，不如 1，保持 dp[5]=1。
右端 i=5 试完，定下 dp[5]=1：整串 "banana" 最少切 1 刀。
全部算完，答案 = dp[5] = 1：banana 切成 b | anana（"anana" 是回文），只需 1 刀。这就是「末段回文则 dp[j−1]+1」逐位递推出来的结果。
边界:整体回文 0;单字符 0;无长回文 n−1。
两个延伸:中心扩展省到 O(n);求方案用回溯、求最优值用 DP。
参考代码
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]复杂度
- 时间：O(n²)，n 是串长。外层 i、内层 j 各 O(n),回文判定借助 pal 表是 O(1),整体 O(n²)
- 空间：O(n²)，pal 回文表占 O(n²),dp 数组占 O(n),合计 O(n²)。也可用「中心扩展」把空间降到 O(n)
易错点
面试追问把动画讲成自己的话
追问能不能不预存 n×n 的 pal 表,把空间降到 O(n)?
追问这道题和「分割回文串 I(枚举所有方案)」有什么本质区别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
单词拆分 II
LeetCode 140 · 困难 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——围绕思路、代码与复杂度继续追问，获得分步反馈
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题