原文链接: https://leetcode-cn.com/problems/palindrome-partitioning-ii
英文原文
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example 1:
Input: s = "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2:
Input: s = "a" Output: 0
Example 3:
Input: s = "ab" Output: 1
Constraints:
1 <= s.length <= 2000sconsists of lower-case English letters only.
中文题目
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab" 输出：1 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a" 输出：0
示例 3：
输入：s = "ab" 输出：1
提示：
1 <= s.length <= 2000s仅由小写英文字母组成
通过代码
高赞题解
动态规划
如果在 131. 分割回文串 有使用到 DP 进行预处理的话。
这道题就很简单了，就是一道常规的动态规划题。
为了方便，我们约定所有下标从 $1$ 开始。
即对于长度为 $n$ 的字符串，我们使用 $[1,n]$ 进行表示。
估计不少看过三叶题解的同学都知道，这样做的目的是为了减少边界情况判断，这本身也是对于「哨兵」思想的运用。
递推「最小分割次数」思路
我们定义 $f[r]$ 为将 $[1,r]$ 这一段字符分割为若干回文串的最小分割次数，那么最终答案为 $f[n]$。
不失一般性的考虑 $f[r]$ 如何转移：
- 从「起点字符」到「第 $r$ 个字符」能形成回文串。那么最小分割次数为 0，此时有 $f[r] = 0$；
- 从「起点字符」到「第 $r$ 个字符」不能形成回文串。此时我们需要枚举左端点 $l$，如果 $[l,r]$ 这一段是回文串的话，那么有 $f[r] = f[l - 1] + 1$。
在 $2$ 中满足回文要求的左端点位置 $l$ 可能有很多个，我们在所有方案中取一个 $\min$ 即可。
快速判断「任意一段子串是否回文」思路
剩下的问题是，我们如何快速判断连续一段 $[l, r]$ 是否为回文串，做法和昨天的 131. 分割回文串 一模一样。
PS. 在 131. 分割回文串，数据范围只有 $16$，因此我们可以不使用 DP 进行预处理，而是使用双指针来判断是否回文也能过。但是该题数据范围为 $2000$（数量级为 $10^3$），使用朴素做法判断是否回文的话，复杂度会去到 $O(n^3)$（计算量为 $10^9$），必然超时。
因此我们不可能每次都使用双指针去线性扫描一遍 $[l, r]$ 判断是否回文。
一个合理的做法是，我们先预处理出所有的 $g[l][r]$，$g[l][r]$ 代表 $[l,r]$ 这一段是否为回文串。
预处理 $g[l][r]$ 的过程可以用递推去做。
要想 $g[l][r] = true$ ，必须满足以下两个条件：
- $g[l + 1][r - 1] = true$
- $s[l] = s[r]$
由于状态 $g[l][r]$ 依赖于状态 $g[l + 1][r - 1]$，因此需要我们左端点 $l$ 是「从大到小」进行遍历；而右端点 $r$ 是「从小到大」进行遍历。
因此最终的遍历过程可以整理为：右端点 $r$ 一直往右移动（从小到大），在 $r$ 固定情况下，左端点 $l$ 在 $r$ 在左边开始，一直往左移动（从大到小）。
代码：
[]class Solution { public int minCut(String s) { int n = s.length(); char[] cs = s.toCharArray(); // g[l][r] 代表 [l,r] 这一段是否为回文串 boolean[][] g = new boolean[n + 1][n + 1]; for (int r = 1; r <= n; r++) { for (int l = r; l >= 1; l--) { // 如果只有一个字符，则[l,r]属于回文 if (l == r) { g[l][r] = true; } else { // 在 l 和 r 字符相同的前提下 if (cs[l - 1] == cs[r - 1]) { // 如果 l 和 r 长度只有 2；或者 [l+1,r-1] 这一段满足回文，则[l,r]属于回文 if (r - l == 1 || g[l + 1][r - 1]) { g[l][r] = true; } } } } } // f[r] 代表将 [1,r] 这一段分割成若干回文子串所需要的最小分割次数 int[] f = new int[n + 1]; for (int r = 1; r <= n; r++) { // 如果 [1,r] 满足回文，不需要分割 if (g[1][r]) { f[r] = 0; } else { // 先设定一个最大分割次数（r 个字符最多消耗 r - 1 次分割） f[r] = r - 1; // 在所有符合 [l,r] 回文的方案中取最小值 for (int l = 1; l <= r; l++) { if (g[l][r]) f[r] = Math.min(f[r], f[l - 1] + 1); } } } return f[n]; } }
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n^2)$
关于「如何确定状态定义」
有同学会对「如何确定 DP 的状态定义」有疑问，觉得自己总是定不下 DP 的状态定义。
首先，十分正常，不用担心。
DP 的状态定义，基本上是考经验的（猜的），猜对了 DP 的状态定义，基本上「状态转移方程」就是呼之欲出。
虽然大多数情况都是猜的，但也不是毫无规律，相当一部分是定义是与「结尾」和「答案」有所关联的。
例如本题定义 $f[i]$ 为以下标为 $i$ 的字符作为结尾（结尾）的最小分割次数（答案）。
因此对于那些你没见过的 DP 模型题，可以从这两方面去「猜」。
Manacher（非重要补充）
如果你还学有余力的话，可以看看下面这篇题解。
提供了「回文串」问题的究极答案：Manacher 算法。
由于 Manacher 算法较为局限，只能解决「回文串」问题，远不如 KMP 算法使用广泛，不建议大家深究原理，而是直接当做「模板」背过。
背过这样的算法的意义在于：相当于大脑里有了一个时间复杂度为 $O(n)$ 的 api 可以使用，这个 api 传入一个字符串，返回该字符串的最大回文子串。
如果觉得自己背不下来，也没有问题。事实上我还没有见过必须使用 Manacher 算法才能过的回文串题。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 51579 | 104694 | 49.3% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 分割回文串 | 中等 |
