题目：132.分割回文串Ⅱ
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a"
输出：0
示例 3：
输入：s = "ab"
输出：1
提示：
1 <= s.length <= 2000s仅由小写英文字母组成
题目解读--参考灵神
一、寻找子问题
原问题描述：
给定一个字符串s（例如s = "aabb"），我们的目标是把它分割成若干个子串，使得每个子串都是回文串，并且要找到满足这个条件的最少分割次数。子问题的产生方式：
为了找到最少分割次数，我们可以通过枚举分割出的最右边那段子串的长度（或者左端点）来产生子问题。以s = "aabb"为例：当分割出最右边子串为
b时，因为b是回文串（单个字符本身就是回文串），此时我们就得到了一个新的子问题：如何把剩下的字符串aab分割成一些子串，使每个子串都是回文串，并求出最少分割次数。当分割出最右边子串为
bb时，bb是回文串，那么新的子问题就是：如何把字符串aa分割成回文子串并求出最少分割次数。当分割出最右边子串为
abb时，由于abb不是回文串（从左到右和从右到左顺序不同），这种情况不符合我们的要求，不产生子问题。当分割出最右边子串为
aabb时，aabb不是回文串，同样不产生子问题。
这些新产生的子问题和原问题的性质是相似的，只是问题规模变小了（字符串长度变短了），所以可以使用递归的方式来解决。这里从右往左思考子问题的产生，主要是为了后续方便将递归算法转化为递推算法，当然从左往右思考也是可行的。
判断子串是否为回文串的方法：
对于一个子串s[l]到s[r]（表示字符串s中从索引l到索引r的子串），我们通过分类讨论来判断它是否为回文串：如果
s[l]不等于s[r]，那么这个子串肯定不是回文串，因为回文串要求从左到右和从右到左读起来是一样的，两端字符不相等就不满足回文串的定义。如果
s[l]等于s[r]，那么判断这个子串是否为回文串的问题就转化为判断子串s[l + 1]到s[r - 1]是否为回文串。这又是一个和原问题相似但规模更小的子问题，同样可以使用递归的方法来解决。
二、状态定义与状态转移方程
状态定义：
定义dfs(r)表示把字符串s的前缀s[0]到s[r]分割成一些子串，使每个子串都是回文串的最少分割次数。这里的r是字符串的索引，表示考虑到了字符串的第r个字符（索引从 0 开始）。状态转移方程推导：
为了计算dfs(r)，我们需要枚举分割出的最右边那段子串的左端点l（0 <= l <= r）。如果子串
s[l]到s[r]是回文串，那么我们可以在l - 1和l之间切一刀，将字符串s[0]到s[r]分成了两部分：s[0]到s[l - 1]和s[l]到s[r]。此时，我们接下来需要解决的子问题就是把前缀s[0]到s[l - 1]分割成回文子串的最少分割次数，即dfs(l - 1)。因为我们要找到最少分割次数，所以需要对所有可能的
l取值情况进行比较，取其中的最小值。用公式表示就是：dfs(r) = min(dfs(l - 1) + 1)，其中l从 0 到r取值，+1表示在l - 1和l之间切一刀，这算作 1 次分割操作。
递归边界：
如果字符串s[0]到s[r]本身就是回文串（可以通过前面判断子串是否为回文串的方法来判断），那么就无需进行分割，直接返回 0，即dfs(r) = 0。递归入口：
原问题是求整个字符串s分割成回文子串的最少分割次数，所以递归的入口是dfs(n - 1)，其中n是字符串s的长度，dfs(n - 1)的返回值就是我们要求的答案。判断回文串的函数定义：
定义isPalindrome(l, r)表示子串s[l]到s[r]是否为回文串。如果
s[l]不等于s[r]，那么子串肯定不是回文串，直接返回false。如果
s[l]等于s[r]，那么判断子串是否为回文串的问题就转化为isPalindrome(l + 1, r - 1)，即继续判断去掉两端字符后的子串是否为回文串。递归边界：当
l等于l时（即子串长度为 1），或者l等于l - 1时（即子串为空串），都认为是回文串，返回true。
三、递归搜索 + 保存递归返回值 = 记忆化搜索
在整个递归过程中，会存在大量重复的递归调用（即递归函数的入参相同）。因为递归函数没有副作用（即相同的输入不会因为调用次数不同而产生不同的输出），所以同样的入参无论计算多少次，结果都是一样的。
为了避免重复计算，提高算法效率，我们可以使用记忆化搜索来优化：
当一个状态（即递归函数的入参）是第一次遇到时，在递归函数返回结果之前，把这个状态及其对应的结果记录到一个
memo数组（或其他数据结构）中。当一个状态不是第一次遇到时（即
memo数组中已经保存了该状态对应的结果，结果不等于memo数组的初始值），就直接返回memo数组中保存的结果，而不需要再次进行递归计算。
在 Python 中，我们可以直接使用 @cache 装饰器来实现记忆化搜索的功能，它会自动帮我们处理上述缓存和查询的操作，无需手动编写 memo 数组相关的代码。
题解
分割回文串Ⅱ算法
class Solution:
def minCut(self, s: str) -> int:
# 定义一个内部函数 is_palindrome，用于判断字符串 s 中从索引 l 到索引 r 的子串是否为回文串
# @cache 装饰器会缓存函数的返回值，避免对相同参数的重复计算，提高效率
@cache
def is_palindrome(l: int, r: int) -> bool:
# 递归边界：当 l >= r 时，说明子串为空串或长度为 1，空串和长度为 1 的字符串都是回文串，返回 True
if l >= r:
return True
# 如果子串两端的字符 s[l] 和 s[r] 相等，则递归判断去掉两端字符后的子串 s[l+1] 到 s[r-1] 是否为回文串
# 如果两端字符不相等，则该子串不是回文串，返回 False
return s[l] == s[r] and is_palindrome(l + 1, r - 1)
# 定义一个内部函数 dfs，用于计算将字符串 s 的前缀 s[0] 到 s[r] 分割成回文子串的最少分割次数
# @cache 装饰器同样用于缓存该函数的返回值，避免重复计算
@cache
def dfs(r: int) -> int:
# 如果字符串 s 的前缀 s[0] 到 s[r] 已经是回文串（通过调用 is_palindrome(0, r) 判断）
# 那么不需要进行分割，直接返回 0
if is_palindrome(0, r):
return 0
# 初始化最少分割次数 res 为正无穷大，后续通过比较找到真正的最少分割次数
res = float('inf')
# 枚举分割位置 l，从 1 到 r（因为至少要分割一次，所以 l 从 1 开始）
for l in range(1, r + 1):
# 如果子串 s[l] 到 s[r] 是回文串（通过调用 is_palindrome(l, r) 判断）
if is_palindrome(l, r):
# 计算将字符串 s 的前缀 s[0] 到 s[l-1] 分割成回文子串的最少分割次数（递归调用 dfs(l - 1)）
# 并加上在 l-1 和 l 之间切一刀的分割次数 1，然后与当前的最少分割次数 res 比较，取较小值
res = min(res, dfs(l - 1) + 1)
# 返回最终计算得到的将字符串 s 的前缀 s[0] 到 s[r] 分割成回文子串的最少分割次数
return res
# 调用 dfs(len(s) - 1)，计算将整个字符串 s 分割成回文子串的最少分割次数，并返回结果
# 因为 dfs(r) 计算的是前缀 s[0] 到 s[r] 的情况，当 r = len(s) - 1 时，就是整个字符串 s 的情况
return dfs(len(s) - 1) 时间复杂度分析
整体时间复杂度结论：
时间复杂度为 O(n^2)，其中 n 是字符串 s 的长度。这里使用了动态规划相关的分析方法，即动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。dfs函数的时间复杂度分析：状态个数：
dfs函数的状态个数等于 O(n)。因为dfs(r)中r的取值范围是从0到n - 1（n为字符串长度），总共n种不同的状态，对应着字符串不同长度的前缀，所以状态个数是线性级别的，为 O(n)。单个状态的计算时间：在计算
dfs(r)时，需要枚举分割位置l来判断子串是否为回文串，l从1到r取值，最多有n种可能（当r = n - 1时），即单个状态的计算时间为 O(n)。综合计算：根据上述动态规划时间复杂度的计算方法，
dfs函数的时间复杂度就是状态个数 O(n) 乘以单个状态的计算时间 O(n)，结果为O(n^2)。
isPalindrome函数的时间复杂度分析：状态个数：
isPalindrome(l, r)函数用于判断子串s[l]到s[r]是否为回文串，l可以取0到n - 1共n个值，对于每个l，r可以取l到n - 1之间的值，这样总的状态组合数是 n+(n−1)+...+1=2n(n+1)，近似为O(n^2)。单个状态的计算时间：在判断子串是否为回文串时，虽然是递归判断，但由于使用了记忆化（
@cache装饰器），相同状态不会重复计算，每次查询直接返回结果，所以单个状态的计算时间为 O(1)。综合计算：
isPalindrome函数的时间复杂度是状态个数O(n^2) 乘以单个状态的计算时间 O(1)，结果同样为O(n^2)。
由于算法主要由这两个函数构成，且它们的时间复杂度都是O(n^2)，所以整体时间复杂度为O(n^2)。
空间复杂度分析
空间复杂度为O(n^2)，原因是需要保存各个状态的值，无论是 dfs 函数还是 isPalindrome 函数的状态。dfs 函数有 O(n) 个状态，isPalindrome 函数有O(n^2)个状态，综合起来，保存这些状态就需要O(n^2)量级的空间 。