# 0132. 分割回文串 II
### 题目地址(132. 分割回文串 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 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
