难度: Hard
给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab" 输出：1 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a" 输出：0
示例 3：
输入：s = "ab" 输出：1
提示：
1 <= s.length <= 2000s 仅由小写英文字母组成注意：本题与主站 132 题相同： https://leetcode-cn.com/problems/palindrome-partitioning-ii/
运行时间: 152 ms
内存: 16.0 MB
class Solution:
def minCut(self, s: str) -> int:
results = [i-1 for i in range(len(s)+1)]
for i in range(len(s)):
for j in range(len(s)-i):
b = i - j
e = i + j
if b < 0 or e >= len(s): break
if s[b] != s[e]: break
results[e+1] = min(results[e+1], results[b]+1)
for j in range(len(s)-i):
b = i - j
e = i + j + 1
if b < 0 or e >= len(s): break
if s[b] != s[e]: break
results[e+1] = min(results[e+1], results[b]+1)
return results[len(s)]
本题解利用动态规划来计算分割字符串s成回文子串所需的最少分割次数。使用一个列表results，其中results[i]代表字符串s的前i个字符组成的子串分割成回文子串所需的最小次数。初始化results[i] = i - 1，意味着最坏情况下（即每个字符都需要分割），分割次数是i-1。接着，利用两个嵌套循环分别以每个字符为中心扩展寻找回文串。第一个循环寻找以s[i]为中心的奇数长度的回文子串，第二个循环寻找偶数长度的回文子串。若找到回文，则更新results[e+1]（e为回文串的终点），使其为results[b] + 1的最小值，这里b是回文串的起点。这样，通过更新results数组，最终results[len(s)]即为将整个字符串s分割成回文子串所需的最少次数。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def minCut(self, s: str) -> int:
results = [i-1 for i in range(len(s)+1)] # 初始化dp数组，results[i]是s的前i个字符所需的最小分割次数
for i in range(len(s)):
for j in range(len(s)-i):
b = i - j # 回文起始位置
e = i + j # 回文结束位置
if b < 0 or e >= len(s): break # 边界检查
if s[b] != s[e]: break # 不是回文则终止
results[e+1] = min(results[e+1], results[b]+1) # 更新dp数组
for j in range(len(s)-i):
b = i - j # 回文起始位置
e = i + j + 1 # 回文结束位置
if b < 0 or e >= len(s): break # 边界检查
if s[b] != s[e]: break # 不是回文则终止
results[e+1] = min(results[e+1], results[b]+1) # 更新dp数组
return results[len(s)] # 返回整个字符串所需的最小分割次数
在动态规划中，`results[i] = i - 1`的初始化反映了字符串s的前i个字符在最坏情况下的分割次数。这是基于每个字符都独立成为一个回文子串的假设，即每个字符之间都需要一个分割。例如，对于字符串`abc`，最坏情况下需要分割成`a|b|c`，这需要两次分割，所以`results[3] = 2`。这种初始化确保了在动态规划过程中，我们总是从最大可能的分割次数开始优化，逐步寻找减少分割次数的可能，直到找到最小的分割次数。其他的初始化值要么不能覆盖所有情况，要么不符合问题的最坏情况设定。
当找到一个回文子串`s[b:e+1]`时，`results[e+1]`的更新操作用`min`函数来确保我们记录到目前为止找到的以`e+1`为结束点的子串的最小分割次数。这里，`results[e+1] = min(results[e+1], results[b] + 1)`比较了当前记录的`results[e+1]`和新发现的回文子串的分割次数（即`results[b] + 1`，这里+1代表从b到e的这一段）。这种方法确保了每次都是取最小值，因此可以覆盖所有可能的分割方案，不会遗漏更优的分割。这是因为动态规划算法本质上是在考虑所有可能的分割方式，并实时更新到达每个位置的最小分割数。
在这种特定的扩展中心方法中，我们是从中心向两边扩展来检查回文。在每次扩展时，我们只需检查`s[b]`与`s[e]`是否相等。如果相等，并且由于我们是从中心向外扩展，那么内部的字符串已经在之前的扩展中被验证为回文。例如，如果`s[b+1]`到`s[e-1]`是回文，并且`s[b]`等于`s[e]`，则`s[b]`到`s[e]`也必然是回文。这种方法确保了我们不会遇到中间部分不是回文的情况，因为我们是逐步验证每一个子回文串的。