回文分割 II
将预先计算的回文表与一维 DP 结合，找出将字符串分割成多个回文串所需的最少切分次数。
回文分割 II 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
问题：最少切分次数
回文分割 II 要求：给定字符串 s，找出最少的切分次数，使分割后的每个子串都是回文。对于 'aab'，切分一次即可得到 ['aa', 'b']，因此答案是 1。对于 'a'，答案是 0（它本身已经是回文）。这个问题包含两个 DP 阶段：首先预计算哪些子串是回文，然后使用一维 DP 找出最少切分次数。
阶段 1：预计算回文表
首先使用区间 DP 构建 is_pal[i][j] = True，表示 s[i..j] 是回文。该过程的时间复杂度为 O(n²)，空间复杂度为 O(n²)。另一种方法是使用中心扩展，在 O(n²) 时间内填充同一张表。我们需要这张表，因为一维切分 DP 会反复查询 is_pal[i][j]——预计算可以避免在切分 DP 循环中重复进行回文检查。
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
print(build_palindrome_table('aab'))阶段 2：设置一维切分 DP
将 cuts[i] 定义为分割 s[0..i] 所需的最少切分次数。如果 s[0..i] 本身是回文，则 cuts[i] = 0。否则，尝试每个分割点：对于从 0 到 i-1 的每个 j，如果 s[j+1..i] 是回文，则 cuts[i] = min(cuts[i], cuts[j] + 1)。我们要问的是：如果最后一个分割片段是 s[j+1..i]，情况会怎样？那么前缀需要 cuts[j] 次切分，此外还需要再切分 1 次。
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0 # entire prefix is a palindrome
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]完整解法与跟踪
让我们跟踪 'aab' 的处理过程。回文表：is_pal[0][0]='a'=T、is_pal[1][1]='a'=T、is_pal[2][2]='b'=T、is_pal[0][1]='aa'=T、is_pal[1][2]='ab'=F、is_pal[0][2]='aab'=F。切分次数：cuts[0]=0（'a' 是回文），cuts[1]=0（'aa' 是回文），对于 cuts[2]：'aab' 不是回文，尝试 j=1：is_pal[2][2]=T，因此 cuts[2] = cuts[1]+1 = 1。答案：1。
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]
print(min_cut('aab')) # 1
print(min_cut('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab'))时间与空间复杂度
阶段 1（回文表）的时间复杂度为 O(n²)，空间复杂度为 O(n²)。阶段 2（切分 DP）有一个遍历 n 个位置的外层循环，以及一个遍历 n 个分割点的内层循环，因此时间复杂度同样为 O(n²)。总体而言：时间复杂度为 O(n²)，空间复杂度为 O(n²)。切分次数数组的空间可以降至 O(n)，但回文表仍需要 O(n²) 的空间。面试通常要求 O(n²) 的复杂度——使用 Manacher 算法的 O(n) 解法超出了通常范围。
回文表的中心扩展
除了使用区间 DP 方法构建回文表之外，您还可以使用中心扩展填充 is_pal。对于每个中心位置，向两侧扩展并标记找到的所有回文。该方法的时间复杂度仍为 O(n²)，空间复杂度仍为 O(n²)，但由于缓存行为更好，在实践中可能更快。两种方法在面试中都可行。
def build_pal_expand(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
def expand(l, r):
while l >= 0 and r < n and s[l] == s[r]:
is_pal[l][r] = True
l -= 1; r += 1
for i in range(n):
expand(i, i) # odd-length centres
expand(i, i+1) # even-length centres
return is_pal
print('Expand-around-centre palindrome table built')枚举所有分割（第一部分）
回文分割 I（一个相关问题）要求枚举 ALL 个有效分割，使每个子串都是回文。该方法使用backtracking，并将预计算的回文表作为剪枝判定器。与用于计数的最少切分 DP 不同，它会枚举指数级数量的解，因此需要采用完全不同的方法。
def partition_all(s):
n = len(s)
is_pal = build_pal_expand(s)
result = []
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition_all('aab')) # [['a','a','b'], ['aa','b']]将切分次数初始化为 n-1
一个常见技巧是：将 cuts[i] = i 初始化，而不是初始化为 inf，因为对于 s[0..i]，最坏情况是将每个字符单独切分，此时需要 i 次切分。这样可以避免在代码中检查 inf。当 is_pal[0][i] 为真时，将其覆盖为 0。这样的初始化明确了切分次数的上界，也让代码略微简洁一些。
def min_cut_clean(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n)) # cuts[i] = i (worst case)
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]替代方案：无需单独表的一遍 DP
一种简洁的变体是同时填充回文表和切分 DP。在从每个中心扩展回文时，立即更新 cuts 数组。对于回文 s[l..r]，我们可以更新 cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0))。这样无需单独进行一次 O(n²) 的表遍历，在面试时间紧张时实现起来可能更加简洁。
需要考虑的边界情况
回文分割 II 的关键边界情况包括：(1) 单字符字符串返回 0 次切分；(2) 已经是回文的字符串返回 0 次切分；(3) 所有字符都不相同的字符串需要 n-1 次切分；(4) 所有字符都相同的字符串（例如 'aaaa'）需要 0 次切分，因为整个字符串就是回文。请始终确认您的解法能够正确处理 is_pal[0][i] = True 的提前退出逻辑。
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n))
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]
print(min_cut('a')) # 0
print(min_cut('aaaa')) # 0
print(min_cut('abc')) # 2面试沟通技巧
在面试中讲解这个问题时，请先介绍两阶段方法：首先构建回文表，然后对切分次数数组运行一维 DP。在编写代码之前，先用语言解释递推关系。说明回文表包含 O(n²) 个条目，并且每个条目都可以使用区间 DP 递推关系在 O(1) 时间内填充。在写出完整解法之前，务必先演示您的跟踪示例，以便在压力下证明解法的正确性。
快速检查
测试您对本课数据结构 & 算法 — 编程面试准备相关概念的理解。
课程回顾
在本课中，您学到了：回文分割 II 使用两个 DP 阶段——先预计算回文表，再运行一维切分 DP；对于所有满足 s[j..i] 是回文的 j，切分递推关系为 cuts[i] = min(cuts[j-1] + 1)；以及总体时间复杂度为 O(n²)，空间复杂度为 O(n²)。接下来我们将学习戳气球问题，它使用一种巧妙的逆向区间 DP 方法。
常见问题解答
「回文分割 II」课时是免费的吗？
是的 — 「回文分割 II」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「回文分割 II」这节课中我会学到什么？
将预先计算的回文表与一维 DP 结合，找出将字符串分割成多个回文串所需的最少切分次数。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「回文分割 II」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。