class Solution:
    def minCut(self, s: str) -> int:
        N = len(s)
        if N<2:
            return 0
        matrix = [[True for _ in range(N)] for _ in range(N)]
        for i in range(N):
            matrix[i][i] = True

        for to_add in range(1, len(s)):
            for i in range(N - to_add):
                start, end = i, i + to_add
                matrix[start][end] = matrix[start + 1][end - 1] and s[start] == s[end]

        dp = [0 for _ in range(N)]
        for i in range(1, N):
            if not matrix[0][i]:
                min_cut = dp[i-1] + 1
                for k in range(i-1, -1, -1):
                    if matrix[k][i]:
                        tmp = dp[k-1] + 1
                        min_cut = tmp if tmp < min_cut else min_cut
                dp[i] = min_cut
        return dp[-1]


if __name__=='__main__':
    s = Solution()
    print(s.minCut('aaffe'))
