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，函数可以在
那么，我们就可以使用双层循环枚举所有的子串，并
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] 是回文，那么在其左右加相同的字符，同样可以构成一个回文。在不是回文的字符串左右添加任意字符都不能得到回文串。因此转移方程就是：
palindrome_pairs[i][j] = (s[i] == s[j]) and palindrome_pairs[i + 1][j - 1]这道题有一点被忽略，也算是一个难点吧。回顾下上面的代码：
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:
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)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
