0132：分割回文串 II（★★）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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