# 0132. 分割回文串 II

### 题目地址(132. 分割回文串 II)

<https://leetcode-cn.com/problems/palindrome-partitioning-ii/>

### 题目描述

```
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

 

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。


示例 2：

输入：s = "a"
输出：0


示例 3：

输入：s = "ab"
输出：1


 

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成
```

### 前置知识

* 动态规划

### 公司

* 暂无

### 思路

为了能够得到最小的**分割次数**。我们需要枚举所有的分割可能，从中找到最小的。使用纯粹暴力的回溯并无法通过本题。因此需要性能上更加优秀的算法。

试想，如果 s\[i:j] 是否是回文的信息已经计算好了，关于如何计算，这需要一点点预处理，我会在之后讲解。

现在不妨假设有一个函数 : `judge(i,j)`，你可以输入 i 和 j，函数可以在 $O(1)$ 的时间返回 s\[i:j] 是否为回文，如果是回文则返回 true，否则返回 false。

那么，我们就可以使用双层循环枚举所有的子串，并

```py
for i in range(n):
    for j in range(i + 1, n):
        if judge(i + 1, j):
            # 你的逻辑
```

这里的动态规划转移为： `dp[j] = min(dp[j], dp[i] + 1)`， 其中 dp\[i] 表示将字符串 s\[0:i] 分割成若干回文串的最小分割次数。那么答案自然就是 dp\[n-1]。base case 为 dp\[0] = 0，其他初始化为无穷大即可。

剩下的则是 judge 实现。 实际上，我们可以预处理二维数组 palindrome\_pairs ，其中 palindrome\_pairs\[i]\[j] 存放的是一个布尔值，表示 s\[i:j] 是否是回文， 具体处理的过程也是使用动态规划技巧。其动态规划转移方程思想就是**中心扩展法**，这是一种回文问题中常用的技巧。

这种算法的思想为：如果 s\[i:j] 是回文，那么在其左右加相同的字符，同样可以构成一个回文。在不是回文的字符串左右添加任意字符都不能得到回文串。因此转移方程就是：

```py
palindrome_pairs[i][j] = (s[i] == s[j]) and palindrome_pairs[i + 1][j - 1]
```

这道题有一点被忽略，也算是一个难点吧。回顾下上面的代码：

```py
for i in range(n):
    for j in range(i + 1, n):
        if judge(i + 1, j):
            dp[j] = min(dp[j], dp[i] + 1)
```

这里的代码有个问题，即如果 s\[0:j] 本身就是一个回文，那么 dp\[j] 应该是 0，这也算是一种特殊的 base case。

### 关键点

* 预处理。 将 s\[i:j] 是否为回文的数据提前计算出来存储到一个二维数组中。接下来就是普通的动态规划。
* 如果 s\[0:j] 本身就是一个回文，那么 dp\[j] 应该是 0

### 代码

* 语言支持：Python3

Python3 Code:

```python

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        palindrome_pairs = [[True] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                palindrome_pairs[i][j] = (s[i] == s[j]) and palindrome_pairs[i + 1][j - 1]

        def judge(i, j):
            return palindrome_pairs[i][j]

        dp = [float("inf")] * n
        dp[0] = 0
        for i in range(n):
            for j in range(i + 1, n):
                if palindrome_pairs[0][j]:
                    dp[j] = 0
                elif judge(i + 1, j):
                    dp[j] = min(dp[j], dp[i] + 1)
        return dp[-1]

```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n^2)$
* 空间复杂度：$O(n^2)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/31kxcv.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/132.palindrome-partitioning-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.