132.分割回文串II|最少分割次数

判断回文的公式 s[l]==s[r] and is_huiwen(l+1,r-1) 首先如果0,r是回文直接返回0，不需要分割，然后从左往右，从1开始如果是回文就切一刀最右边是r-1，然后继续判断，取最小，因为过程中有很多重复的过程用@cache记录缓存

132. 分割回文串 II | 最少分割次数 题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的 最少分割次数。

示例 示例 1： 输入: s = "aab" 输出: 1 解释: 只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。 示例 2： 输入: s = "a" 输出: 0 示例 3： 输入: s = "ab" 输出: 1 提示： 1 <= s.length <= 2000s 仅由小写英文字母组成

---

解题思路 1. 直接枚举（超时）

最直观的思路是使用 回溯 + 记忆化搜索 来遍历所有可能的划分方案，并计算最小的分割次数。

但由于字符串长度可达 2000，直接用回溯会 超时，需要更优的方法。

2. 动态规划（最优解）

我们可以使用 动态规划 来优化求解过程。

状态定义 dp[i] 表示 以索引 i 结尾的子串 s[0:i+1] 的最少分割次数。 状态转移 如果 s[0:i] 本身是回文，则不需要分割，dp[i] = 0。否则，我们枚举所有可能的分割点 j，如果 s[j+1:i] 是回文，则 dp[i] = min(dp[i], dp[j] + 1)。 如何快速判断回文

可以 预处理 一个 is_palindrome[i][j] 数组，使 is_palindrome[i][j] = True 表示 s[i:j+1] 是回文。

时间复杂度 预处理回文 O(n^2)动态规划 O(n^2)总体时间复杂度 O(n^2)

---

代码实现（Python） 方法 1：回溯（超时） from typing import List class Solution: def partition(self, s: str) -> List[List[str]]: n = len(s) ans = [] path = [] # 递归函数 def dfs(i: int) -> None: if i == n: ans.append(path.copy()) return for j in range(i, n): a = s[i:j+1] if a == a[::-1]: # 判断是否是回文 path.append(a) dfs(j+1) path.pop() dfs(0) return ans

问题：此方法会生成所有回文划分方案，无法直接求得最小分割次数，且 时间复杂度过高，容易超时。

---

方法 2：动态规划 class Solution: def minCut(self, s: str) -> int: n = len(s) # 预处理回文 is_palindrome = [[False] * n for _ in range(n)] for right in range(n): for left in range(right + 1): if s[left] == s[right] and (right - left <= 2 or is_palindrome[left + 1][right - 1]): is_palindrome[left][right] = True # dp 数组 dp = [float('inf')] * n for i in range(n): if is_palindrome[0][i]: # 整个子串是回文，不需要切割 dp[i] = 0 else: for j in range(i): if is_palindrome[j+1][i]: # 如果 s[j+1:i+1] 是回文 dp[i] = min(dp[i], dp[j] + 1) return dp[n - 1] 代码解析 预处理回文表：is_palindrome[i][j] 预计算 s[i:j+1] 是否是回文。动态规划计算最小分割次数： dp[i] 表示 s[0:i+1] 需要的最小分割次数。若 s[0:i] 本身是回文，则 dp[i] = 0。否则遍历 j，如果 s[j+1:i] 是回文，则 dp[i] = min(dp[i], dp[j] + 1)。 时间复杂度分析 预处理回文：O(n^2)动态规划：O(n^2)总时间复杂度：O(n^2)

---

复杂度对比 方法适用情况时间复杂度是否超时回溯（DFS）小规模数据指数级 O(2^n)超时动态规划任意规模数据O(n^2)通过

---

总结 暴力回溯 只能用于 求所有划分方案，但无法高效求最优解。动态规划（DP） 是 最优解，预处理回文后，可以在 O(n^2) 时间内求解最少分割次数。预处理 is_palindrome 可以减少重复计算，提升性能。

---

📌 动态规划是求解最少分割次数的最佳方法！