分割回文串 II 图解题解
这道题到底在问什么
- 输入
- s="aab"
- 输出
- 1("aa" + "b",切 1 刀)
- 输入
- s="a"
- 输出
- 0(本身就是回文,不用切)
先想最直接的笨办法
记住「枚举最后一段的左端 j,若 s[j..i] 回文就用 dp[j−1]+1 更新 dp[i]」,下面逐位套它。（动画第 3 步）
最优解：一步一步想明白
- 3记住「枚举最后一段的左端 j,若 s[j..i] 回文就用 dp[j−1]+1 更新 dp[i]」,下面逐位套它。
⚠️ 容易写错的地方
✗ 错：每判一次回文都重新 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]
完整代码（Python / C++ / Java）
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];
}
}复杂度
时间
O(n²)
n 是串长。外层 i、内层 j 各 O(n),回文判定借助 pal 表是 O(1),整体 O(n²)
空间
O(n²)
pal 回文表占 O(n²),dp 数组占 O(n),合计 O(n²)。也可用「中心扩展」把空间降到 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 分割回文串 II 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不预存 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,是这对题的分水岭。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 分割回文串 II 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。