132. 分割回文串 II

1. 必须有前面0个字母的回文字串个数，当作边界条件，因为第一个字母可以不作为分割点，如把“aab"分割为[“”,“aab”]，所以dp长度为len(s)+1
2. i 从1开始，s[j:i]不取s[i]的值,s[0:0]则无
3. j 范围为[0,i-1], s前i个字母，起点和终点都最多为i-1

class Solution:def minCut(self, s: str) -> int:dp = [0] + [inf]*(len(s))# dp[i]表示s[:i+1]的最少回文子串个数(即s前i个字母)for i in range(1, len(s)+1):for j in range(i):temp = s[j:i]if temp == temp[::-1]:dp[i] = min(dp[i], dp[j]+1)return dp[-1]-1

优化回文子串判断

1. isPalindromic[i][j]的判断依赖于isPalindromic[i+1][j-1]，所以i递减，j递增

class Solution:def minCut(self, s: str) -> int:isPalindromic = [[False]*len(s) for _ in range(len(s))]for i in range(len(s)-1, -1, -1):for j in range(i, len(s)):if s[i] == s[j] and (j-i <= 1 or isPalindromic[i+1][j-1]):isPalindromic[i][j] = Truedp = [0]+[inf]*(len(s))for i in range(1,len(s)+1):for j in range(i):if isPalindromic[j][i-1]:dp[i] = min(dp[i], dp[j]+1)return dp[-1]-1