def minCut_TLE(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)

        * 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)
        dp = [[1<<32-1 for _ in xrange(length+1)] for _ in xrange(length+1)]
        for i in xrange(length+1):
            try:
                dp[i][i] = 0
                dp[i][i+1] = 0
            except __HOLE__:
                pass

        for i in xrange(length, -1, -1):
            for k in xrange(i, length+1):
                if self.is_palindrome(s[i:k]):
                    dp[i][k] = 0
                else:
                    dp[i][k] = min(1+dp[i][j]+dp[j][k] for j in xrange(i+1, k))

        return dp[0][length]
dataset/ETHPy150Open algorhythms/LeetCode/132 Palindrome Partitioning II.py/Solution.minCut_TLE