§1
题目描述
给定字符串 s,把它分割成若干子串使每个子串都是回文串,返回所需的最少切割次数(切 k 刀得到 k+1 段)。
输入 = s="aab" 输出 = 1("aa" + "b",切 1 刀)
输入 = s="a" 输出 = 0(本身就是回文,不用切)
§2
思路解析动画文字版
记住「枚举最后一段的左端 j,若 s[j..i] 回文就用 dp[j−1]+1 更新 dp[i]」,下面逐位套它。
边界:整体回文 0;单字符 0;无长回文 n−1。
两个延伸:中心扩展省到 O(n);求方案用回溯、求最优值用 DP。
§3
参考代码
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]看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。
§4
复杂度
- 时间：O(n²)，n 是串长。外层 i、内层 j 各 O(n),回文判定借助 pal 表是 O(1),整体 O(n²)
- 空间：O(n²)，pal 回文表占 O(n²),dp 数组占 O(n),合计 O(n²)。也可用「中心扩展」把空间降到 O(n)
§5
易错点
✗ 错误写法：每判一次回文都重新 O(n) 扫一遍
✓ 正确写法：用 pal 区间表 O(1) 查回文
回文判定若每次现扫会让总复杂度升到 O(n³);pal[j][i] 靠里层 pal[j+1][i−1] 递推,查一次 O(1)
✗ 错误写法：dp[i] 初值设成 0 或无穷
✓ 正确写法：初值设成 i(最坏每字符各切)
dp[i] 最坏是把 s[0..i] 切成 i+1 个单字符、切 i 刀;设 0 会漏更新,设无穷需额外处理整段回文的情形
✗ 错误写法：回文判定漏了 i−j≤2 的短串
✓ 正确写法：长度 ≤3 的首尾相等串直接判回文
长度 1、2、3 时去掉首尾后里层为空或单字符、必回文;不特判会去读越界的 pal[j+1][i−1]
§
面试追问把动画讲成自己的话
追问能不能不预存 n×n 的 pal 表,把空间降到 O(n)?
可以,用「中心扩展」边算边更新 dp:枚举每个回文中心(单中心和双中心),向两侧扩展;每扩出一个回文区间 [l, r],就用 dp[l−1]+1 去更新 dp[r]。这样不需要二维 pal 表,空间只用 O(n) 的 dp 数组,时间仍是 O(n²)。代码稍长但更省内存。
追问这道题和「分割回文串 I(枚举所有方案)」有什么本质区别?
I 要列出所有把 s 切成全回文段的方案,是回溯/DFS,答案数量可能指数级,只能枚举;II 只要最少刀数,是最优化问题,有最优子结构(前缀的最优解可由更短前缀推出),所以用 DP,O(n²) 解决。「求方案」用回溯、「求最优值」用 DP,是这对题的分水岭。
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
下一题 · 动态规划套路 56/64
→单词拆分 II
LeetCode 140 · 困难 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
599道动画图解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路？去图解算法专题