動機

Problem

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.

 

Example 1:

Input: s = "aab"Output: 1Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"Output: 0

Example 3:

Input: s = "ab"Output: 1

 

Constraints:

    t
  • 1 <= s.length <= 2000
    • t
  • s consists of lower-case English letters only.

Sol

dp(i)是以i結尾要多少cut

class Solution:
    def minCut(self, s: str) -> int:
        @cache
        def isP(i,j):
            if j-i <= 0:
                return True
            else:
                return s[i]==s[j] and isP(i+1,j-1)
        
        @cache
        def dp(j):
            if j == 0:
                return 0
            elif j == -1:
                return -1
            else:
                return min([dp(i-1)+1 for i in range(j+1) if isP(i,j)])
        return dp(len(s)-1)