132. 分割回文串 II
题目
递归，只不过要遍历所有的子串并且递归，求最小值。仔细看下代码：
递归会超时。
class Solution:
def minCut(self, s: str) -> int:
if s==s[::-1]:
return 0
ans = float('inf')
for i in range(1,len(s)):
if s[:i]==s[:i][::-1]:
ans = min(ans, self.minCut(s[i:])+1)
return ans
因此需要用动态规划。数组min_s记录到字符串到i位置需要分割次数。相当于把之前递归的结果保存了下来，没此到了一个新的i，遍历之前的结果min_s，寻找最小的分割次数。仔细看下代码：
class Solution:
def minCut(self, s: str) -> int:
min_s = list(range(len(s)))
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i+1):
if s[i] == s[j] and (i - j < 2 or dp[j + 1][i - 1]):
dp[j][i] = True
# 说明不用分割
if j == 0:
min_s[i] = 0
else:
min_s[i] = min(min_s[i], min_s[j - 1] + 1)
return min_s[-1]
