本文共 970 字，大约阅读时间需要 3 分钟。

palindrome-partitioning-ii

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s. For example, given s =“aab”, Return1since the palindrome partitioning[“aa”,“b”]could be produced using 1 cut.

题意

即形成回文串的最小割数

思路

没要求列出所有种类，只需求一个割数，首选dp。 一切尽在公式dp[i] = min(dp[j] + 1, dp[i])中，这题还要特别注意初始化dp的技巧。

python实现

class Solution:    def minCut(self, s):        n = len(s)        # 最坏打算        dp = [i-1 for i in range(n+1)]        # 保证要取到整个字符串，不要被下标所困扰        for i in range(1, n+1):            for j in range(i+1):                tmp = s[j:i]                # print(tmp)                if self.isPalindrome(tmp):                    dp[i] = min(dp[j] + 1, dp[i])        return dp[n]    def isPalindrome(self, s):        if s == s[::-1]:            return True        return Falseif __name__ == '__main__':    s = 'aabcc'    # s = 'aabaa'    so = Solution()    print(so.minCut(s))

转载地址：http://mejmb.baihongyu.com/