132. 分割回文串 II
题目描述
输入一个字符串 s。在它上面切若干刀，把它分成几个连续片段，使每个片段都是回文串。
返回最少需要切几刀。如果 s 本身就是回文，返回 0。
示例 1
输入：s = "aab" 输出：1
解释：切一刀得到 aa 和 b。
示例 2
输入：s = "a" 输出：0
解释：单个字符本身是回文，不用切。
示例 3
输入：s = "ab" 输出：1
解释：切一刀得到 a 和 b。
数据范围
1 <= s.length <= 2000s只含小写英文字母。
解题思路：回文表+动态规划
两张表一起填。pal[i][j] 表示 s[i..j] 是否回文：s[i] == s[j] 且（长度 ≤ 2 或 pal[i+1][j-1]）。dp[j] 表示 s[0..j] 的最少刀数，初始为 j（每个字符切一刀）。枚举最后一段回文 s[i..j]：若 i = 0，整段回文，dp[j] = 0；否则 dp[j] = min(dp[j], dp[i-1] + 1)。
为什么正确
外层按 j 增大，内层 i 从小到大；用到的 pal[i+1][j-1] 属于列 j-1，已经算好。
复杂度分析
时间 O(n²)，空间 O(n²)。
易错点
每次重新判断子串是否回文会变成 O(n³)，对 n = 2000 会超时；要用 pal 表记住结果。答案是刀数，不是段数，段数 = 刀数 + 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
pal = [[False] * n for _ in range(n)]
dp = list(range(n))
for j in range(n):
for i in range(j + 1):
if s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1]):
pal[i][j] = True
if i == 0:
dp[j] = 0
else:
dp[j] = min(dp[j], dp[i - 1] + 1)
return dp[n - 1]class Solution {
public int minCut(String s) {
int n = s.length();
boolean[][] pal = new boolean[n][n];
int[] dp = new int[n];
for (int k = 0; k < n; k++) dp[k] = k;
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1])) {
pal[i][j] = true;
if (i == 0) {
dp[j] = 0;
} else {
dp[j] = Math.min(dp[j], dp[i - 1] + 1);
}
}
}
}
return dp[n - 1];
}
}class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool>> pal(n, vector<bool>(n, false));
vector<int> dp(n);
for (int k = 0; k < n; k++) dp[k] = k;
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
if (s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1])) {
pal[i][j] = true;
if (i == 0) {
dp[j] = 0;
} else {
dp[j] = min(dp[j], dp[i - 1] + 1);
}
}
}
}
return dp[n - 1];
}
};func minCut(s string) int {
n := len(s)
pal := make([][]bool, n)
for k := range pal {
pal[k] = make([]bool, n)
}
dp := make([]int, n)
for k := range dp {
dp[k] = k
}
for j := 0; j < n; j++ {
for i := 0; i <= j; i++ {
if s[i] == s[j] && (j-i < 2 || pal[i+1][j-1]) {
pal[i][j] = true
if i == 0 {
dp[j] = 0
} else {
dp[j] = min(dp[j], dp[i-1]+1)
}
}
}
}
return dp[n-1]
}var minCut = function(s) {
const n = s.length;
const pal = Array.from({ length: n }, () => new Array(n).fill(false));
const dp = Array.from({ length: n }, (_, k) => k);
for (let j = 0; j < n; j++) {
for (let i = 0; i <= j; i++) {
if (s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1])) {
pal[i][j] = true;
if (i === 0) {
dp[j] = 0;
} else {
dp[j] = Math.min(dp[j], dp[i - 1] + 1);
}
}
}
}
return dp[n - 1];
};function minCut(s: string): number {
const n = s.length;
const pal = Array.from({ length: n }, () => new Array(n).fill(false));
const dp = Array.from({ length: n }, (_, k) => k);
for (let j = 0; j < n; j++) {
for (let i = 0; i <= j; i++) {
if (s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1])) {
pal[i][j] = true;
if (i === 0) {
dp[j] = 0;
} else {
dp[j] = Math.min(dp[j], dp[i - 1] + 1);
}
}
}
}
return dp[n - 1];
}其他解法
两种解法时间都是 O(n²)；回文表法结构直观，中心扩展法把空间从 O(n²) 降到 O(n)。
解法 2：中心扩展+动态规划 时间 O(n²)，空间 O(n)
dp[j] 表示 s[0..j] 的最少分割次数，初始 dp[j] = j。枚举每个中心，分奇数长度和偶数长度向两边扩展。每扩展出一个回文 s[l..r]，就用 dp[l-1] + 1 更新 dp[r]，l = 0 时 dp[r] = 0。中心从左到右处理，用到的 dp[l-1] 都已经确定。
不需要 n×n 的回文表，空间降到 O(n)。正确性依赖中心的处理顺序，理解难度略高。
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
dp = list(range(n))
for c in range(n):
for l, r in ((c, c), (c, c + 1)):
while l >= 0 and r < n and s[l] == s[r]:
dp[r] = 0 if l == 0 else min(dp[r], dp[l - 1] + 1)
l -= 1
r += 1
return dp[n - 1]class Solution {
public int minCut(String s) {
int n = s.length();
int[] dp = new int[n];
for (int i = 0; i < n; i++) dp[i] = i;
for (int c = 0; c < n; c++) {
for (int k = 0; k < 2; k++) {
int l = c, r = c + k;
while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
dp[r] = l == 0 ? 0 : Math.min(dp[r], dp[l - 1] + 1);
l--;
r++;
}
}
}
return dp[n - 1];
}
}class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<int> dp(n);
for (int i = 0; i < n; i++) dp[i] = i;
for (int c = 0; c < n; c++) {
for (int k = 0; k < 2; k++) {
int l = c, r = c + k;
while (l >= 0 && r < n && s[l] == s[r]) {
dp[r] = l == 0 ? 0 : min(dp[r], dp[l - 1] + 1);
l--;
r++;
}
}
}
return dp[n - 1];
}
};func minCut(s string) int {
n := len(s)
dp := make([]int, n)
for i := range dp {
dp[i] = i
}
for c := 0; c < n; c++ {
for k := 0; k < 2; k++ {
l, r := c, c+k
for l >= 0 && r < n && s[l] == s[r] {
if l == 0 {
dp[r] = 0
} else {
dp[r] = min(dp[r], dp[l-1]+1)
}
l--
r++
}
}
}
return dp[n-1]
}var minCut = function(s) {
const n = s.length;
const dp = Array.from({ length: n }, (_, i) => i);
for (let c = 0; c < n; c++) {
for (let k = 0; k < 2; k++) {
let l = c, r = c + k;
while (l >= 0 && r < n && s[l] === s[r]) {
dp[r] = l === 0 ? 0 : Math.min(dp[r], dp[l - 1] + 1);
l--;
r++;
}
}
}
return dp[n - 1];
};function minCut(s: string): number {
const n = s.length;
const dp: number[] = Array.from({ length: n }, (_, i) => i);
for (let c = 0; c < n; c++) {
for (let k = 0; k < 2; k++) {
let l = c, r = c + k;
while (l >= 0 && r < n && s[l] === s[r]) {
dp[r] = l === 0 ? 0 : Math.min(dp[r], dp[l - 1] + 1);
l--;
r++;
}
}
}
return dp[n - 1];
}