132. 分割回文串 II

简单分析

输入的参数是字符串s，返回值是最小的切割次数。那这个问题的典型解法应该是动态规划，因为我们需要找最优解，而每一步的选择可能会影响后面的结果，但可以通过子问题的最优解来构建整体最优解。

那么动态规划的状态如何定义呢？通常这种情况下，dp[i]表示前i个字符的最小分割次数。例如，对于字符串s的长度为n的情况，我们需要计算dp[n]。初始条件的话，如果整个字符串本身就是回文的，那么不需要分割，也就是dp[0]=0（这里可能需要调整索引）。

接下来需要考虑状态转移方程。对于每一个位置i，我们要检查所有可能的j（j < i），看看s[j..i-1]是否是回文。如果是的话，那么dp[i]可以取dp[j]+1中的最小值。这里的逻辑是因为如果在j处已经有一个最优解，再加上当前这一段的回文分割，就能得到i处的候选答案。

不过这样的话，时间复杂度会不会很高呢？比如，对于每个i都要遍历前面所有的j，并且每次判断回文都需要O(n)的时间，这样总的时间复杂度会是O(n^3)，这在n较大的情况下可能会有问题。比如当n=1000时，这显然不行。但是原题的测试数据规模是多少呢？题目中没有给出具体限制，可能需要考虑优化。

这时候就需要想办法减少判断回文的次数。常用的方法是预处理出一个二维数组is_palindrome，其中is_palindrome[i][j]表示s从i到j是否为回文。这样预处理之后，可以在O(1)的时间内查询任意区间的回文情况。而预处理本身可以用中心扩展法或者动态规划的方法完成，时间复杂度是O(n²)。

步骤大致清晰：

1. 预处理出所有可能的回文区间。
2. 使用动态规划计算每个位置的最小分割次数。

具体的实现步骤是怎样的呢？

首先是预处理回文表。

以动态规划的方式来做的话，可以这样定义：对于单个字符来说，肯定是回文；两个相同字符也是回文。然后对于更长的子串，s[i...j]是回文的条件是s[i] == s[j]且中间的部分s[i+1...j-1]也是回文。因此，我们可以按子串长度从小到大填充这个表格。

另一种方法是用中心扩展，即对每个可能的中心和奇偶长度进行处理，向两边扩展直到不是回文为止。这种方法可能在某些情况下更快，但在最坏情况下还是O(n²)。

不管哪种方式，预处理得到is_palindrome数组是关键的一步。

创建二维数组palindrome，大小n x n。初始化所有长度为1和2的情况。然后按照长度递增的顺序填充其余部分。

预处理回文表：使用动态规划预处理出所有可能的回文子串，存储在一个二维数组 is_palindrome 中，其中 is_palindrome[i][j] 表示子串 s[i...j] 是否为回文

然后进行动态规划。

初始化dp数组，其中dp[0] = -1吗？或者说，假设字符串的前0个字符的分割次数是-1？比如，当i=0时，对应空字符串，此时分割次数为-1，这样在后续的计算中，比如当某个子串s[0...k]是回文时，可以直接用dp[k+1] = dp[0] + 1 = 0次分割。这可能更方便一些。

例如，假设字符串长度为n，则dp数组的大小是n+1，其中dp[i]代表前i个字符的最小分割次数。初始时，dp[0] = -1，其他设为无穷大。然后对于每个i，从1到n，我们查看所有j从0到i-1的位置，如果s[j...i-1]是回文的话，那么dp[i] = min(dp[i], dp[j] + 1)。最终结果是dp[n]的值

举个例子，假设字符串是"a"。那么预处理后is_palindrome[0][0]=true。初始化dp数组为inf，除了dp[0]=-1。当i=1时，j可以是0，此时s[0..0]是回文，所以dp[1] = dp[0]+1 = 0。正确，分割次数是0次，无需分割。

另一个例子，"ab"。这时，预处理后的is_palindrome[0][0]=true，is_palindrome[1][1]=true，is_palindrome[0][1]=false。那么对于i=1，只能是j=0的情况，分割次数0。i=2的时候，尝试j=0和j=1。j=0时，子串是ab，不是回文。j=1时，子串是b，是回文。所以dp[2] = dp[1]+1=1。即分割一次，分成a和b。

动态规划求解最小分割次数：定义 dp[i] 表示前 i 个字符的最小分割次数。初始化 dp[0] = -1（空字符串的分割次数视为-1），其余位置初始化为无穷大。遍历每个位置 i，检查所有可能的起始位置 j，若 s[j...i-1] 是回文，则更新 dp[i] = min(dp[i], dp[j] + 1)

class Solution:def minCut(self, s: str) -> int:n = len(s)# 创建一个大小为 n×n 的布尔矩阵，初始值全为 True# g[i][j] 表示子串 s[i...j] 是否为回文，初始设为 True 是因为空字符串和单个字符均被视为回文。g = [[True] * n for _ in range(n)]#  # 从末尾向前遍历起始索引 ifor i in range(n - 1, -1, -1):# 遍历结束索引 j（j > i）for j in range(i + 1, n):# 确保在处理子串 s[i...j] 时，其内部子串 s[i+1...j-1] 已经被计算过。# 状态转移方程g[i][j] 为真当且仅当：# s[i] 和 s[j] 字符相同，# 且去掉首尾后的子串 s[i+1...j-1] 也是回文（由 g[i+1][j-1] 决定）g[i][j] = (s[i] == s[j]) and g[i + 1][j - 1]# 这段代码利用动态规划预处理结果g来计算将字符串s的前i+1个字符分割成回文子串所需的最小分割次数，存储在数组f中f = [float("inf")] * nfor i in range(n):if g[0][i]:f[i] = 0else:#需要分割，遍历所有可能的切分点jfor j in range(i):if g[j + 1][i]:f[i] = min(f[i], f[j] + 1)return f[n - 1]