q21.py 文件源码

def get_min_cut(cls, strs):
        if not strs:
            return 0

        length = len(strs)
        dp = [0 for _ in range(length+1)]
        dp[length] = -1
        is_palindrome = [[False for _ in range(length)] for _ in range(length)]

        i = length - 1
        while i >= 0:
            dp[i] = sys.maxsize
            j = i
            while j < length:
                if strs[i] == strs[j] and (j - i < 2 or is_palindrome[i+1][j-1]):
                    dp[i] = min([dp[i], dp[j+1]+1])
                    is_palindrome[i][j] = True
                j += 1
            i -= 1

        return dp[0]