132.md

132. Palindrome Partitioning II

Solution 1 (O(n^2))

# Dynamic Programming
class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        info = [[False for _ in range(len(s))] for _ in range(len(s))]
        for right in range(len(s)):
            for left in range(right + 1):
                if s[left] == s[right] and (right - left <= 2 or info[left + 1][right - 1]):
                    info[left][right] = True
        dp = [i for i in range(len(s))]
        for i in range(1, len(s)):
            if info[0][i]:
                dp[i] = 0
                continue
            dp[i] = min(dp[j] + 1 for j in range(i) if info[j + 1][i])
        return dp[len(s) - 1]