https://leetcode.cn/problems/palindrome-partitioning-ii/

dp[i] 表示 s[0..i] 切分为回文子串的最小分割次数

dp[i] = min(dp[j] + 1) , 如果 s[j+1...i]是回文串, j < i

dp[i] 表示 s[i...]的最小分割次数, dp[0]为要求的结果

dp[i] = dp[j] + 1， 如果 s[i...j-1]是回文串，i < j

 def minCut(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n+1)
        dp[n] = -1

        pail = [[False]*n for _ in range(n)]
        for i in range(n-1, -1, -1):
            dp[i] = float("inf")
            for j in range(i, n):
                if s[i] == s[j] and (j - i + 1 <=2 or pail[i+1][j-1] == True):
                    pail[i][j] = True
                    dp[i] = min(dp[j+1]+1, dp[i])
        
        print(dp)
        return dp[0]