给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a"
输出：0
示例 3：
输入：s = "ab"
输出：1
提示：
- 1 <= s.length <= 2000
- s 仅由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
动态规划：
状态定义：dp[i] 是以第 i 位为结尾的字符串的最少分割次数。
转移方程：dp[i] = min 0≤j<i {dp[j]} + 1，其中 s[j + 1...i] 是回文字符串。
返回值：dp[len(s)-1]
可使用 g[i][j] = g[i+1][j-1] and s[i] == s[j] 判断是否为回文串。
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
g = [[True]*n for _ in range(n)]
# 记录 i，j 是否为回文串
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
g[i][j] = s[i] == s[j] and g[i + 1][j - 1]
f = [float("inf")] * n
for i in range(n):
# 如果 0...i 是回文串，切割 0 次
if g[0][i]:
f[i] = 0
else:
for j in range(i):
if g[j + 1][i]:
f[i] = min(f[i], f[j] + 1)
return f[n - 1]
- 时间复杂度 O(n^2)：n 是字符串长度，计算 g 和 f 的都是双循环。
- 空间复杂度 O(n^2)：n 是字符串长度，数组 g 需要 O(n^2) 的空间，数组 f 需要 O(n) 的空间。