<doocs>0132.Palindrome Partitioning II_1.py
def minCut( s: str) -> int:
    n = len(s)
    dp1 = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            dp1[i][j] = s[i] == s[j] and (j - 1 < 3 or dp1[i + 1][j - 1])
    dp2 = [0] * n
    for i in range(n):
        if not dp1[0][i]:
            dp2[i] = i
            for j in range(1, i + 1):
                if dp1[j][i]:
                    dp2[i] = min(dp2[i], dp2[j - 1] + 1)
    return dp2[-1]
def sample_funcname ( var_0 : str ) -> int :
    var_4 = len ( var_0 )
    var_8 = [ [ False ] * var_4 for var_6 in range ( var_4 ) ]
    for var_10 in range ( var_4 - 1 , - 1 , - 1 ) :
        for var_11 in range ( var_10 , var_4 ) :
            var_8 [ var_10 ] [ var_11 ] = var_0 [ var_10 ] == var_0 [ var_11 ] and ( var_11 - 1 < 3 or var_8 [ var_10 + 1 ] [ var_11 - 1 ] )
    var_14 = [ 0 ] * var_4
    for var_10 in range ( var_4 ) :
        if not var_8 [ 0 ] [ var_10 ] :
            var_14 [ var_10 ] = var_10
            for var_11 in range ( 1 , var_10 + 1 ) :
                if var_8 [ var_11 ] [ var_10 ] :
                    var_14 [ var_10 ] = min ( var_14 [ var_10 ] , var_14 [ var_11 - 1 ] + 1 )
    return var_14 [ - 1 ]
