## 题目地址(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://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
