def minCut_dp(self, s):
        """
        dp

        a   b   a   b   b   b   a   b   b   a   b   a
                    i                       k
        if s[i:k+1] is palindrome, #cut is 0; otherwise
        cut s[i:k+1] into palindrome, the #cut:
          cut the s[i:k+1] to two parts
          cut the left part into palindrome, #cut is dp[i, j]
          cut the right part into palindrome, #cut is dp[j+1, k+1]
        find the minimum for above

        dp[i, n+1] = min(dp[i, j]+dp[j, k+1]+1)

        when drawing the matrix, you will find it difficult to construct it at one shot (especially, vertical line)


        To avoid TLE, use 1-d dp instead of 2-d dp
        D[i] represents #cut for s[i:length+1]
        if s[i:j] is palindrome and we need #cut for s[j:] is D[j], then
        for minimum: D[i] = min(D[j+1]+1) for all j

        To avoid TLE, use dp for determination of palindrome
        Determine s[i:k+1] is palindrome:
        P[i, k+1] = P[i+1, k] && s[i]==s[k]

        * another algorithm is dfs with global_min
        * to tell s[i:k+1] whether it is palindrome can be optimized by dp
        :param s: str
        :return: int
        """
        if not s:
            return 0

        length = len(s)
        # palindrome dp
        P = [[False for _ in xrange(length+1)] for _ in xrange(length+1)]
        for i in xrange(length+1):
            try:
                P[i][i] = True
                P[i][i+1] = True
            except IndexError:
                pass

        for i in xrange(length, -1, -1):
            for j in xrange(i+2, length+1):
                try:
                    P[i][j] = P[i+1][j-1] and s[i] == s[j-1]
                except __HOLE__:
                    P[i][j] = True

        # min cut dp
        D = [length-i-1 for i in xrange(length)]  # max is all cut
        for i in xrange(length-1, -1, -1):
            if P[i][length]:
                D[i] = 0
            else:
                for j in xrange(i+1, length):
                    if P[i][j]:
                        D[i] = min(D[i], D[j]+1)
        return D[0]
dataset/ETHPy150Open algorhythms/LeetCode/132 Palindrome Partitioning II.py/Solution.minCut_dp