> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/132-fen-ge-hui-wen-chuan-ii.md).

# \[132]\[困难]\[DFS]\[回溯]\[动态规划] 分割回文串 II

## 题目描述

[132. 分割回文串 II](https://leetcode-cn.com/problems/palindrome-partitioning-ii/)

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

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

示例:

输入: "aab" 输出: 1 解释: 进行一次分割就可将 s 分割成 \["aa","b"] 这样两个回文子串。

## 解题思路

### 回溯

回溯的思路同[\[131\]\[中等\]\[DFS\]\[回溯\]\[动态规划\] 分割回文串](/garnet/suan-fa/dong-tai-gui-hua/131-fen-ge-hui-wen-chuan.md)一样. 但由于要求返回最少分割次数, 我们将每次分割看作深度搜索树向下推荐了一层, 因此DFS的过程还要传递当前的层数.

* 不用再记录所有可能的分割结果, 而是需要维护一个最少层数, 当产生完整的分割结果时, 比较当前的分割结果推进了多少层, 如果比之前的少, 则更新方案, 否则不接受
* 剪枝规则增加, 如果当前递归层数已经大于已有方案的层数, 就可以停止递归而回溯了, 因为继续找下去的结果肯定也是无用的
  * 为了让最小层数尽快出现, 增加剪枝效率, 迭代时首先考虑最长的分割方案, 然后将分割子字符串逐渐缩小

```python
class Solution:
    def minCut(self, s: str) -> int:
        self.s = s
        self.n = len(s)
        if self.n == 0:
            return []

        self.level = float('inf')
        self.result = []
        self.dfs(0, [], 0)
        return self.level - 1

    def dfs(self, i, path, level):
        if i == self.n:
            if level < self.level:
                self.level = level
                self.result = path[:]

        if level >= self.level:
            return

        for j in range(self.n - 1, i - 1, -1):
            if self.s[i:j+1] == self.s[i:j+1][::-1]:
                path.append(self.s[i:j + 1])
                self.dfs(j + 1, path, level + 1)
                path.pop()
```

但回溯的方法时间复杂度依然很高, python提交超时.

### 动态规划

定义一位状态数组dp\[i]代表的意思是将\[0, i]\(包括i)代表的子字符串, 分割成一些子串, 使每个子串都是回文串, 对应的最小分割次数. 因此题目最后的答案就是dp\[n - 1], n是字符串的长度.

初始化dp\[0], 由于是第一个字符, 不需要分割就是一个回文串, 因此对应的分割次数为0.

对于dp\[i]的递推, 如果\[j, i]是一个回文串, 那么有dp\[i] = dp\[j] + 1. 可能有多个后缀都是回文串, 因此要逐位遍历, 判断对应后缀是否是回文子串, 记录最小的结果, 及dp\[i] = min(dp\[i], dp\[j] + 1).

另外还有两个点:

* 计算dp\[i], 还要判断\[0, i]整个子串是否是回文串, 如果是, 也不用分割, 对应的dp\[i]为0, 且可以剪枝, 不再继续搜索下去了
* 在初始化时将每个位置的dp\[i]置为一个很大的值, 方便统一判断

判断s\[j, i]是否是回文串的方法, 可以使用同[\[131\]\[中等\]\[DFS\]\[回溯\]\[动态规划\] 分割回文串](/garnet/suan-fa/dong-tai-gui-hua/131-fen-ge-hui-wen-chuan.md)中动态规划的方法, 提前计算好每两个位置的结果. 可以是简单将字符串与反转后的字符串比较, 只不过这样时间复杂度高一些.

```python
class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0

        dp = [float('inf')] * n
        dp[0] = 0

        for i in range(1, n):
            if s[:i + 1] == s[:i + 1][::-1]:
                dp[i] = 0
                continue

            for j in range(i):
                if s[j + 1: i + 1] == s[j + 1: i + 1][::-1]:
                    dp[i] = min(dp[i], dp[j] + 1)
        return dp[-1]
```

## 参考资料

* 动态规划: [132. 分割回文串 II【动态规划】详解](https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/132-fen-ge-hui-wen-chuan-iidong-tai-gui-6fyn1/)