132.分割回文串Ⅱ

题目：132.分割回文串Ⅱ

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

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

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

• 1 <= s.length <= 2000

• s 仅由小写英文字母组成

题目解读--参考灵神

一、寻找子问题

1. 原问题描述：
   给定一个字符串 s（例如 s = "aabb"），我们的目标是把它分割成若干个子串，使得每个子串都是回文串，并且要找到满足这个条件的最少分割次数。

2. 子问题的产生方式：
   为了找到最少分割次数，我们可以通过枚举分割出的最右边那段子串的长度（或者左端点）来产生子问题。以 s = "aabb" 为例：

   • 当分割出最右边子串为 b 时，因为 b 是回文串（单个字符本身就是回文串），此时我们就得到了一个新的子问题：如何把剩下的字符串 aab 分割成一些子串，使每个子串都是回文串，并求出最少分割次数。

   • 当分割出最右边子串为 bb 时，bb 是回文串，那么新的子问题就是：如何把字符串 aa 分割成回文子串并求出最少分割次数。

   • 当分割出最右边子串为 abb 时，由于 abb 不是回文串（从左到右和从右到左顺序不同），这种情况不符合我们的要求，不产生子问题。

   • 当分割出最右边子串为 aabb 时，aabb 不是回文串，同样不产生子问题。

这些新产生的子问题和原问题的性质是相似的，只是问题规模变小了（字符串长度变短了），所以可以使用递归的方式来解决。这里从右往左思考子问题的产生，主要是为了后续方便将递归算法转化为递推算法，当然从左往右思考也是可行的。

3. 判断子串是否为回文串的方法：
   对于一个子串 s[l] 到 s[r]（表示字符串 s 中从索引 l 到索引 r 的子串），我们通过分类讨论来判断它是否为回文串：

   • 如果 s[l] 不等于 s[r]，那么这个子串肯定不是回文串，因为回文串要求从左到右和从右到左读起来是一样的，两端字符不相等就不满足回文串的定义。

   • 如果 s[l] 等于 s[r]，那么判断这个子串是否为回文串的问题就转化为判断子串 s[l + 1] 到 s[r - 1] 是否为回文串。这又是一个和原问题相似但规模更小的子问题，同样可以使用递归的方法来解决。

二、状态定义与状态转移方程

1. 状态定义：
   定义 dfs(r) 表示把字符串 s 的前缀 s[0] 到 s[r] 分割成一些子串，使每个子串都是回文串的最少分割次数。这里的 r 是字符串的索引，表示考虑到了字符串的第 r 个字符（索引从 0 开始）。

2. 状态转移方程推导：
   为了计算 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 次分割操作。

3. 递归边界：
   如果字符串 s[0] 到 s[r] 本身就是回文串（可以通过前面判断子串是否为回文串的方法来判断），那么就无需进行分割，直接返回 0，即 dfs(r) = 0。

4. 递归入口：
   原问题是求整个字符串 s 分割成回文子串的最少分割次数，所以递归的入口是 dfs(n - 1)，其中 n 是字符串 s 的长度，dfs(n - 1) 的返回值就是我们要求的答案。

5. 判断回文串的函数定义：
   定义 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)  

时间复杂度分析

1. 整体时间复杂度结论：
   时间复杂度为 O(n^2)，其中 n 是字符串 s 的长度。这里使用了动态规划相关的分析方法，即动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。

2. 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)。

3. 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)量级的空间 。